本文共 1282 字，大约阅读时间需要 4 分钟。
#include#include #include #include using namespace std;const int maxn = 1005;const int INF = 99999;int graph[maxn][maxn];int root[maxn];int sign[maxn];int t, n, ans;void Dijkstra(){ ans = 0; memset(sign, 0, sizeof(sign)); for(int i = 1; i <= n; i ++) root[i] = graph[1][i]; sign[1] = 1; for(int cnt = 2; cnt <= n; cnt ++) { int min_num = INF; int minn = 1; for(int i = 1; i <= n; i ++) if(!sign[i] && root[i] < min_num) { min_num = root[i]; minn = i; } sign[minn] = 1; if(min_num == INF) break; for(int i = 1; i <= n; i ++) root[i] = min(root[minn] + graph[minn][i], root[i]); }}int main(){ while(~scanf("%d %d", & t, & n)) { for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) graph[i][j] = INF; while(t --) { int a, b, c; scanf("%d %d %d", & a, & b, & c); if(c < graph[a][b]) graph[a][b] = graph[b][a] = c; } Dijkstra(); printf("%d\n", root[n]); } return 0;}
题意：
输入t, n。n表示地标的个数。之后t行输入a b c。ab代表地标标号。c代表ab距离。求1到n的最短距离。 题解： Dijkstra。转载地址：http://jctpi.baihongyu.com/