Dijkstra优先队列优化：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = ; int head[maxn], dis[maxn], cnt, n, m; bool vis[maxn]; struct edge { int v, w, next; }Edge[maxn]; struct node { int point, distance; node(){} node(int _point, int _distance) {point = _point; distance = _distance;} bool operator < (const node &other)const { return distance > other.distance; } }; void add_Edge(int u, int v, int w) { Edge[cnt].v = v; Edge[cnt].w = w; Edge[cnt].next = head[u]; head[u] = cnt++; } void Dijkstra(int s) { for(int i = 0; i <= n; i++) dis[i] = INF; memset(vis, false, sizeof(vis)); dis[s] = 0; priority_queue<node> q; q.push(node(s, dis[s])); while(!q.empty()) { node now = q.top(); q.pop(); if(vis[now.point]) continue; vis[now.point] = true; for(int i = head[now.point]; i != -1; i = Edge[i].next) { int to = Edge[i].v; if(dis[to] > dis[now.point] + Edge[i].w) { dis[to] = dis[now.point] + Edge[i].w; q.push(node(to, dis[to])); } } } } int main() { int u, v, w; while(scanf("%d%d", &n, &m) != EOF) { if(n == 0 && m == 0) break; cnt = 0; memset(head, -1, sizeof(head)); while(m--) { scanf("%d%d%d", &u, &v, &w); add_Edge(u, v, w); add_Edge(v, u, w); } Dijkstra(1); cout << dis[n] << endl; } return 0; }spfa:
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<string> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = ; int n, m; struct edge { int v, w, next; //edge(){} //edge(int _v, int _w):v(_v), w(_w){} }Edge[maxn]; int head[maxn], dis[maxn], time[maxn], cnt; bool vis[maxn]; void add_Edge(int u, int v, int w) { Edge[cnt].v = v; Edge[cnt].w = w; Edge[cnt].next = head[u]; head[u] = cnt++; } int spfa(int s, int tol) { memset(dis, 63, sizeof(dis)); memset(time, 0, sizeof(time)); memset(vis, false, sizeof(vis)); dis[s] = 0; vis[s] = true; time[s]++; queue<int> q; q.push(s); while(!q.empty()) { int tem = q.front(); q.pop(); vis[tem] = false; for(int i = head[tem]; i != -1; i = Edge[i].next) { int to = Edge[i].v; if(dis[to] > dis[tem] + Edge[i].w) { //cout << "yes\n"; dis[to] = dis[tem] + Edge[i].w; if(!vis[to]) { vis[to] = true; q.push(to); time[to]++; if(time[to] >= tol) return -1; } } } } return dis[n]; } int main() { int u, v, w; while(scanf("%d%d", &n, &m) != EOF) { cnt = 0; memset(head, -1, sizeof(head)); for(int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); add_Edge(u, v, w); add_Edge(v, u, w); } int ans = spfa(1, n); } return 0; }