本文共 1593 字，大约阅读时间需要 5 分钟。
题目：
题意：给定一张图，问起点到终点的最短路。
思路：dijkstra板子题。
很久没有写最短路了。总结一下dijkstra的步骤吧。
d数组用于表示当前最短路径，vis数组用于标记当前点是否已经在最短路集合中了。
每次找到一个d最小的节点，表示他已经无法更短了，把他加入集合，用他去更新其他的节点。一共做n-1次。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 13 #define inf 0x3f3f3f3f14 using namespace std;15 typedef long long LL;16 typedef pair pr;17 18 int t, c, ts, te;19 const int maxn = 2500;20 const int maxm = 6205;21 struct edge{22 int to, nxt, cost;23 }e[maxm * 2];24 int head[maxn], tot;25 26 void add(int x, int y, int w)27 {28 e[++tot].to = y;29 e[tot].cost = w;30 e[tot].nxt = head[x];31 head[x] = tot;32 e[++tot].to = x;33 e[tot].cost = w;34 e[tot].nxt = head[y];35 head[y] = tot;36 }37 38 bool vis[maxn];39 int d[maxn]; 40 void dijkstra()41 {42 memset(d, 0x3f, sizeof(d));43 for(int i = head[ts]; i; i = e[i].nxt){44 d[e[i].to] = e[i].cost;45 }46 vis[ts] = true;47 d[ts] = 0;48 for(int i = 1; i < t; i++){49 int min = inf, min_id;50 for(int j = 1; j <= t; j++){51 if(d[j] < min && !vis[j]){52 min = d[j];53 min_id = j;54 }55 }56 vis[min_id] = true;57 for(int i = head[min_id]; i; i = e[i].nxt){58 if(d[e[i].to] > min + e[i].cost){59 d[e[i].to] = min + e[i].cost;60 }61 }62 }63 }64 65 int main()66 {67 scanf("%d%d%d%d", &t, &c, &ts, &te);68 for(int i = 0; i < c; i++){69 int rs, re, ci;70 scanf("%d%d%d", &rs, &re, &ci);71 add(rs, re, ci);72 }73 74 dijkstra();75 printf("%d\n", d[te]);76 }
转载于:https://www.cnblogs.com/wyboooo/p/11088157.html