Problem Description
输入T，N分别代表有T条通道，和N个地点。接下来T行u,v,w分别表示u地点于v地点之间通道消费,有重复边
Sample Input
5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100
Sample Output
90
代码：dijkstra，就不带注解了，详细算法学习可以百度，只为留个模板复习用
#include<cstdio> using namespace std; const int INF = 0x3f3f3f3f; int Map[1005][1005], n; int vis[1005], dist[1005]; void dijkstra(int u) { int i, Min, j, k; for(i = 1; i <= n; i++) { vis[i] = 0; dist[i] = Map[u][i]; } vis[u] = 1; for(i = 1; i < n; i++) { Min = INF; for(j = 1; j <= n; j++) { if(Min > dist[j] && !vis[j]) { Min = dist[j]; u = j; } } vis[u] = 1; for(k = 1; k <= n; k++) { if(dist[k] > dist[u] + Map[u][k] && Map[u][k] != INF && !vis[k]) { dist[k] = dist[u] + Map[u][k]; } } } printf("%d\n", dist[1]); } int main() { int T, i, j, u, v, w; while(~scanf("%d %d", &T, &n)) { for(i = 0; i <= n; i++) { for(j = 0; j <= n; j++) { if(i == j) Map[i][j] = 0; else Map[i][j] = INF; } } while(T--) { scanf("%d %d %d", &u, &v, &w); if(Map[u][v] > w) Map[u][v] = Map[v][u] = w; } dijkstra(n); } return 0; }bellman_Ford
#include<cstdio> #include<cstring> using namespace std; const int INF = 0x3f3f3f3f; struct node { int u, v, w; }; node Map[2005]; int n, m, dist[1005]; void bellman_Ford(int u) { int i, j; for(i = 1; i <= n; i++) { dist[i] = INF; } dist[u] = 0; for(i = 1; i <= n - 1; i++) { for(j = 1; j <= m; j++) { if(dist[Map[j].v] > dist[Map[j].u] + Map[j].w) dist[Map[j].v] = dist[Map[j].u] + Map[j].w; if(dist[Map[j].u] > dist[Map[j].v] + Map[j].w) dist[Map[j].u] = dist[Map[j].v] + Map[j].w; } } printf("%d\n", dist[1]); } int main() { int i; while(~scanf("%d %d", &m, &n)) { for(i = 1; i <= m; i++) { scanf("%d %d %d", &Map[i].u, &Map[i].v, &Map[i].w); } bellman_Ford(n); } return 0; }Spfa + 前向星
#include<cstdio> #include<queue> #include<cstring> using namespace std; const int INF = 0x3f3f3f3f; struct node { int to, w, next; }; node Map[40005]; int n, head[1005]; int vis[1005], dist[1005]; void spfa(int u) { int i, to, w; queue<int> q; for(i = 1; i <= n; i++) { vis[i] = 0; dist[i] = INF; } vis[u] = 1; dist[u] = 0; q.push(u); while(!q.empty()) { u = q.front(); q.pop(); vis[u] = 0; for(i = head[u]; ~i; i = Map[i].next) { to = Map[i].to, w = Map[i].w; if(dist[to] > dist[u] + w) { dist[to] = dist[u] + w; if(!vis[to]) { vis[to] = 1; q.push(to); } } } } printf("%d\n", dist[1]); } int main() { int T, u, v, w; while(~scanf("%d %d", &T, &n)) { memset(head, -1, sizeof(head)); int cnt = 0; while(T--) { scanf("%d %d %d", &u, &v, &w); Map[cnt].to = v; Map[cnt].w = w; Map[cnt].next = head[u]; head[u] = cnt++; Map[cnt].to = u; Map[cnt].w = w; Map[cnt].next = head[v]; head[v] = cnt++; } spfa(n); } return 0; }dijkstra + 优先队列
#include<cstdio> #include<cstring> #include<vector> #include<queue> #define INF 0x3f3f3f using namespace std; struct node { int to, w; bool operator < (const node &b) const { if(w == b.w) return to < b.to; return w > b.w; } }; int n, x, dist[1005]; vector<node> a[1005]; void dijkstra(int s) { memset(dist, INF, sizeof(dist)); dist[s] = 0; priority_queue<node> q; q.push((node){s, dist[s]}); while(!q.empty()) { node u = q.top(); q.pop(); for(int i = 0; i < a[u.to].size(); i++) { node v = a[u.to][i]; if(dist[v.to] > dist[u.to] + v.w) { dist[v.to] = dist[u.to] + v.w; q.push((node){v.to, dist[v.to]}); } } } printf("%d\n", dist[1]); } int main() { int m, u, v, w; while(~scanf("%d %d", &m, &n)) { while(m--) { scanf("%d %d %d", &u, &v, &w); a[u].push_back((node){v, w}); a[v].push_back((node){u, w}); } dijkstra(n); } return 0; }