http://tyvj.cn/p/1031
求ts到te的最短路径即可
代码为dijkstra
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int G[2505][2505]; int dis[2505]; int visit[2505]; int main () { int t,c,ts,te; scanf("%d%d%d%d", &t, &c, &ts, &te); memset(G, 27, sizeof(G)); for (int i=1;i<=c;i++) { int rs,re,ci; scanf("%d%d%d", &rs, &re, &ci); G[rs][re]=G[re][rs]=ci; } memset(dis, 27, sizeof(dis)); dis[ts] = 0; memset(visit, false, sizeof(visit)); for (int i=1;i<=t-1;i++) { int mini = 10000000; int k = 0; for(int j=1;j<=t;j++) { if (!visit[j]&&dis[j]<mini) { mini = dis[j]; k = j; } } if (k==0) break; visit[k] = true; for (int j=1;j<=t;j++) { if (dis[j]>dis[k]+G[k][j]) { dis[j] = dis[k]+G[k][j]; } } } printf("%d\n", dis[te]); return 0; }
