题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5294
用Dijkstra求出所有点到起点的最短路径
然后 如果dist[u]-dist[v]==w 说明该边可能是在最短路径中，但这种方法会掺入一些没用的 ，不联通的边
然后利用网络流，求出最大流就是最小割了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=3000+5;
const int INF=0x3f3f3f3f;
int N,M;//网络流
struct Node{int to,flow,next;
}nodes[maxn*60];
int NHead[maxn],Ntot;
bool vis[maxn];
void Add_Node(int u,int v,int flow){nodes[Ntot]=Node{v,flow,NHead[u]};NHead[u]=Ntot++;nodes[Ntot]=Node{u,0,NHead[v]};NHead[v]=Ntot++;
}
int DFS(int u,int t,int MinFlow)
{if(u==t) return MinFlow;vis[u]=true;for(int i=NHead[u];i!=-1;i=nodes[i].next){int flow=nodes[i].flow,v=nodes[i].to;if(!vis[v]&&flow>0){int MinF=DFS(v,t,min(MinFlow,flow));if(MinF>0){nodes[i].flow-=MinF; //更新流量 nodes[i^1].flow+=MinF; //添加反向边 return MinF;}}}return 0;
}
int Dinic(){int MaxFlow=0;for(;;){memset(vis,false,sizeof(vis));int Augment=DFS(1,N,INF);if(Augment==0) break;else MaxFlow+=Augment;}return MaxFlow;
}//find the shortest path
struct Edge{int to,weight,next;
}edges[maxn*60];
int Head[maxn],tot;
void Add_Edge(int u,int v,int w){edges[tot]=Edge{v,w,Head[u]};Head[u]=tot++;edges[tot]=Edge{u,w,Head[v]};Head[v]=tot++;
}
struct HeapNode{ //prority_queue 中的优先级 int u,dist; //dist: u点到起点的最短路 ,u: 有向边的终点 HeapNode(int u,int d):u(u),dist(d){}bool operator < (const HeapNode& h) const {return dist>h.dist;}
};
bool done[maxn];
int dist[maxn];
int minB[maxn];
void Dijkstra(int s)
{priority_queue<HeapNode> Q;memset(dist,INF,sizeof(dist));memset(minB,INF,sizeof(minB));memset(done,false,sizeof(done));dist[s]=0;minB[s]=0; Q.push(HeapNode(s,0));while(!Q.empty()){int u=Q.top().u; Q.pop();if(done[u]) continue;done[u]=true;for(int i=Head[u];i!=-1;i=edges[i].next){Edge& e=edges[i];int v=e.to ,w=e.weight;if(dist[v]==dist[u]+w){minB[v]=min(minB[v],minB[u]+1); continue;}if(done[v]) continue;if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;minB[v]=minB[u]+1;Q.push(HeapNode(v,dist[v]));}}}
}//build the shorest path
void getPath()
{memset(NHead,-1,sizeof(NHead)); Ntot=0;for(int u=1;u<=N;u++){for(int i=Head[u];i!=-1;i=edges[i].next){int v=edges[i].to,w=edges[i].weight;if(dist[v]-dist[u]==w)Add_Node(u,v,1);}}
}
int main()
{int u,v,w;while(scanf("%d%d",&N,&M)!=EOF){memset(Head,-1,sizeof(Head)); tot=0;for(int i=0;i<M;i++){scanf("%d%d%d",&u,&v,&w);Add_Edge(u,v,w);}Dijkstra(1);getPath();printf("%d %d\n",Dinic(),M-minB[N]); }return 0;
}