重新手敲下最短路的代码。。
- bellman-ford
- dijkstra
- floyd
- spfa(bellman-ford+queue)
- dijkstra+heap(priority_queue)
怕自己堆敲不出来 - -........用的STL。
拿 HDOJ 2544 验的代码。
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<string> #include<vector> #include<queue> #include<map> #include<algorithm> using namespace std; inline int Rint() { int x; scanf("%d", &x); return x; } #define FOR(i, a, b) for(int i=(a); i<=(b); i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define REP(x) for(int i=0; i<(x); i++) typedef long long int64; #define INF (1<<30) const double eps = 1e-8; #define bug(s) cout<<#s<<"="<<s<<" " #define MAXN 102 #define MAXM 10002 struct node { int u, v, w; } edge[MAXM]; int head[MAXN], next[MAXM]; int idx; int n, m; void init() { idx = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v, int w) { edge[idx].u = u; edge[idx].v = v; edge[idx].w = w; next[idx] = head[u]; head[u] = idx++; } int dist[MAXN]; // bellman_ford,O(nm) void bellman_ford(int st) { REP(n) dist[i] = i==st? 0 : INF; FOR(k, 1, n-1) { FOR(e, 0, idx-1) { int u = edge[e].u, v = edge[e].v; dist[v] = min(dist[v], dist[u]+edge[e].w); } } } // dijkstra,O(n^2) int ins[MAXN]; void dijkstra(int st) { memset(ins, 0, sizeof(ins)); REP(n) dist[i] = i==st? 0 : INF; REP(n) { int u=-1; FOR(j, 0, n-1) if(!ins[j]) { if(u==-1) u=j; u = dist[u]>dist[j]? j : u; } ins[u] = 1; for(int e=head[u]; e!=-1; e=next[e]) { int v = edge[e].v; dist[v] = min(dist[v], dist[u]+edge[e].w); } } } // floyd,点对,O(n^3) int dis[MAXN][MAXN]; void readgraph() { FOR(i, 0, n-1) FOR(j, 0, n-1) { dis[i][j] = INF>>1; } REP(m) { int u = Rint(); int v = Rint(); int w = Rint(); u--, v--; dis[u][v] = min(dis[u][v], w); dis[v][u] = dis[u][v]; } } void floyd() { FOR(k, 0, n-1) FOR(i, 0, n-1) FOR(j, 0, n-1) { dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]); } } // spfa (bellman-ford + queue),O(km),k~=2 int que[MAXN], front, tail; int inq[MAXN]; void spfa(int st) { front = tail = 0; memset(inq, 0, sizeof(inq)); REP(n) dist[i] = i==st? 0 : INF; que[(tail++)%MAXN] = st; inq[st] = 1; while(front%MAXN != tail%MAXN) { int u = que[(front++)%MAXN]; inq[u] = 0; for(int e=head[u]; e!=-1; e=next[e]) { int v = edge[e].v; if(dist[v]>dist[u]+edge[e].w) { dist[v] = dist[u]+edge[e].w; if(!inq[v]) { // 加了这个,才能保证queue里不超过n个点 que[(tail++)%MAXN] = v; inq[v] = 1; } } } } } // dijkstra + heap(STL,priority_queue),O(nlogn) typedef pair<int,int> pii; #define mp(a,b) make_pair((a),(b)) priority_queue<pii, vector<pii>, greater<pii> > q; /* priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数: priority_queue<Type, Container, Functional> 其中Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。 Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list. STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。 */ void dijkstra_heap(int st) { memset(ins, 0, sizeof(ins)); REP(n) dist[i] = i==st? 0 : INF; q.push(mp(dist[st], st)); while(!q.empty()) { pii p = q.top(); q.pop(); int u = p.second; if(ins[u]) continue; ins[u] = 1; for(int e=head[u]; e!=-1; e=next[e]) { int v = edge[e].v; if(dist[v]>dist[u]+edge[e].w) { dist[v] = dist[u]+edge[e].w; q.push(mp(dist[v], v)); } } } } // HDOJ 2544 int main() { while(scanf("%d%d", &n, &m)!=-1 && (n+m)) { init(); REP(m) { int u = Rint(); int v = Rint(); int w = Rint(); u--, v--; addedge(u, v, w); addedge(v, u, w); } // bellman_ford(0); // dijkstra(0); // spfa(0); dijkstra_heap(0); printf("%d\n", dist[n-1]); // readgraph(); // floyd(); // printf("%d\n", dis[0][n-1]); } }