几个最短路算法。
http://acm.hdu.edu.cn/showproblem.php?pid=2544大水题一枚，仅以练手。
Dijkstra:
#include<iostream>using namespace std;#define SIZE 200#define INF 0xfffffff#define MIN(a,b) a>b?b:aint G;int d;int vis;int N,M;int minV(){ int i,v; for(i=0;i<N;i++) { if(!vis) { v = i; break; } } for(;i<N;i++) if(!vis&&d>d) v = i; return v;}int Dijkstra(int s){ memset(vis,0,sizeof(vis)); for(int i=0;i<N;i++)d=INF; d = 0; for(int i=0;i<N;i++) { int v = minV(); vis = true; for(int u=0;u<N;u++) { if(G) { d = MIN(d,d+G); } } } return d;}int main(){ while(cin>>N>>M,N||M) { for(int i=0;i<N;i++) for(int j=0;j<N;j++) G = INF; int a,b; for(int i=0;i<M;i++) { int c; cin>>a>>b>>c; a--,b--; if(c<G) G = G = c; } cout<<Dijkstra(0)<<endl; } return 0;}
Dijkstra+Priority_Queue:
#include<iostream>#include<queue>using namespace std;struct node{int v;int dis;node(){}node(int vv,int diss):v(vv),dis(diss){}bool operator<(const node &n) const{ return dis>n.dis;}};typedef priority_queue<node> PQ;const int SIZE = 110;const int INF = 0xfffffff;int vis;int dis;int G;#define MIN(a,b) a>b?b:avoid init(){ memset(vis,0,sizeof(vis)); for(int i=0;i<SIZE;i++)dis=INF; for(int i=0;i<SIZE;i++) for(int j=0;j<SIZE;j++) G = INF;}int Dijkstra(int s,int n){ dis = 0; PQ pq; pq.push(node(s,dis)); for(int i=0;i<n;i++) { int v; do { if(pq.empty())return INF; v = pq.top().v; pq.pop(); }while(vis); vis = 1; for(int j=0;j<n;j++) { if(G) { dis = MIN(dis,dis+G); pq.push(node(j,dis)); } } } return dis;}int main(){ int n,m; while(cin>>n>>m,n||m) { init(); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; a--,b--; if(G>c) G=G=c; } cout<<Dijkstra(0,n)<<endl; } return 0;}
Floyd:
#include<iostream>using namespace std;const int SIZE = 110;int G;const int INF = 0xfffffff;#define rep(n,i) for(int i=0;i<n;i++)void init(int n){ rep(n,i) { rep(n,j)G = INF; }}int Floyd(int n){ rep(n,k) { rep(n,i) { rep(n,j) { if(G>G+G) { G = G+G; } } } } return G;}int main(){ int n,m; while(cin>>n>>m,n||m) { int a,b,c; init(n); rep(m,i) { cin>>a>>b>>c; a--,b--; if(G>c) { G = G = c; } } cout<<Floyd(n)<<endl; } return 0;}
Bellman_Ford:
#include<iostream>using namespace std;struct Edge{ int s,e; Edge(){} Edge(int ss,int ee):s(ss),e(ee){}};const int SIZE = 20010;Edge edge;int G;int d;void init(){ for(int i=0;i<110;i++) for(int j=0;j<110;j++) G = 0xfffffff,d=0xfffffff;}void Relax(int u,int v){ if(d>d+G) d = d+G;}void Bellman_Ford(int n,int m){ d = 0; for(int i=0;i<n-1;i++) { for(int j=0;j<m;j++) Relax(edge.s,edge.e); }}int main(){ int n,m; while(cin>>n>>m,n||m) { init(); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; a--,b--; if(G>c) { G = G = c; } } int cnt = 0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(G!=0xfffffff) { edge.s = i; edge.e = j; cnt++; } } Bellman_Ford(n,cnt); cout<<d<<endl; } return 0;}
SPFA:
#include<iostream>using namespace std;#include<queue>#define N 110#define INF 0xfffffffint vis;int map;int d;void spfa(int s,int n){ memset(vis,0,sizeof(vis)); memset(d,127,sizeof(d)); d = 0; vis = 1; queue<int> q; q.push(s); while(!q.empty()) { int v = q.front(); q.pop(); vis = 0; for(int i=0;i<n;i++) { if(map) { if(map+d<d) { d = map+d; if(!vis) { vis = 1; q.push(i); } } } } }}int main(){ int n,m; while(cin>>n>>m,n||m) { memset(map,0,sizeof(map)); for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; a--,b--; if(map==0||map>c) map = map = c; } spfa(0,n); cout<<d<<endl; } return 0;}
页:
[1]