//Dijkstra#include <iostream>#include <stdio.h>using namespace std;#define max 0x7fffffff //设置图中的两点的距离为无穷大#define arraysize 2001int dis[arraysize][arraysize];bool final[arraysize];int d[arraysize];int T,N;void Dij(){ for(int i1=1;i1<N;++i1) { d[i1] = dis[N][i1]; } d[N] = 0; final[N] = true; dis[N][N]=0; for(int i2=1;i2<N;++i2) { int min = max; int v = N; for(int i4=1;i4<N;++i4) { if(!final[i4] && min>d[i4]) { min = d[i4]; v = i4; } } final[v] =true; for(int i3=1;i3<N;++i3) { if(!final[i3] && dis[v][i3]!=max) //此处判断是否不可达 { if(d[v]+dis[v][i3]<d[i3]) d[i3] = d[v] + dis[v][i3]; } } } cout<<d[1]<<endl;}int main(){ //freopen("1.txt","r",stdin); while(cin>>T>>N) { for(int i1=1;i1<=N;i1++) { for(int j1=1;j1<=N;j1++) dis[i1][j1] = max; //初始化dis，将距离设为最大 } memset(final,0,sizeof(final)); memset(d,0,sizeof(d)); int start,end,w; for(int i=0;i<T;++i) { cin>>start>>end>>w; if(w<dis[start][end]) //注此处一定要注意判断是否有重边 { dis[start][end] = w; //无向图 dis[end][start] = w; } } Dij(); } //fclose(stdin); return 0;}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/04/25/1720689.html
相关资源：数据结构—成绩单生成器