【SinGuLaRiTy-1002】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
Dijkstra:
题目描述
有向图的单源点最短路问题（Dijkstra算法）
输入
第1行：2个空格分开的整数n(2<=n<=500)和m(10<=m<=20000)，分别表示图的顶点数和边数。
第2..m+1行：每行3个空格分开的整数i，j， w。i表示一条边的起点，j表示终点， w表示权值。
第m＋2行：2个整数s，t(1<=s，t<=n),表示指定的顶点。
输出
第1行：最小距离
第2行：最短路径（从起点到终点的序列，用1个空格分开）
| 样例输入 | 样例输出 |
|
5 7 1 2 10 1 4 30 1 5 100 2 3 50 3 5 10 4 3 20 4 5 60 1 5 |
60 1 4 3 5 |
代码：
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; int n,m; int G[501][501],dis[501],L[501]; bool used[501]; void Dijkstra(int s) { for(int i=1;i<=n;i++) { used[s]=1; for(int j=1;j<=n;j++) { if(G[s][j]==0||s==j) continue; if(dis[j]>dis[s]+G[s][j]) dis[j]=dis[s]+G[s][j],L[j]=s; } int themin=0x3f3f3f3f; for(int i=1;i<=n;i++) if(used[i]==0&&dis[i]<themin) s=i,themin=dis[i]; } } int main() { int a,b,c,S,E,cnt=1; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); G[a][b]=c; } scanf("%d%d",&S,&E); int e=E; dis[S]=0; for(int i=1;i<=n;i++) if(i!=S) dis[i]=0x3f3f3f3f; Dijkstra(S); printf("%d ",dis[E]); while(L[E]!=0) { dis[cnt++]=L[E]; E=L[E]; } for(int i=cnt-1;i>=1;i--) printf("%d ",dis[i]); printf("%d",e); return 0; }
SPAF：
题目描述
有向图的单源点最短路径问题。源点编号为1，终点编号为n。
输入
第1行：2个空格分开的整数n(2<=n<=5000)和m(10<=m<=500000)，分别表示图的顶点数和边数。
第2..m+1行：每行3个空格分开的整数i，j， w。i表示一条边的起点，j表示终点， w表示权值。
输出
第1行：1个整数，表示最小距离
| 样例输入1 | 样例输出1 |
|
4 7
1 2 68
1 3 19
1 4 66
2 3 23
3 4 65
3 2 57
4 1 68
|
66 |
|
样例输入 |
样例输出 |
|
3 3
1 2 -7
2 3 4
3 1 2
|
No Solution |
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct node{ int v,w,next; }edge[500050]; int cnt,head[5050],n,m,dis[5050],tot[5050]; bool inq[5050]; void addedge(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } bool SPFA() { memset(dis,0x3f,sizeof dis); dis[1]=0; inq[1]=1; deque<int>q; q.push_front(1); while(!q.empty()) { int u=q.front(); q.pop_front(); inq[u]=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v,w=edge[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!inq[v]) { if(dis[v]<dis[u])q.push_front(v); else q.push_back(v); inq[v]=1; if(++tot[v]>n)return 0; } } } } return 1; } int main() { int u,v,w; scanf("%d%d",&n,&m); memset(head,-1,sizeof head); for(int i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } SPFA()?printf("%d ",dis[n]): puts("No Solution"); }
Floyd：
代码：
#include<cstdio> #include<cstring> #define maxn 100 #define INF -1 int map[maxn][maxn]; int n, m, path[maxn][maxn]; void Floyd(int n) { int i, j, k; for(k = 0; k < n; ++k) for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) if(map[i][k] != INF && map[k][j] != INF && (map[i][k] + map[k][j] < map[i][j] || map[i][j] == INF)){ map[i][j] = map[i][k] + map[k][j]; path[i][j] = k; } } void getPath(int v, int u) { int k = path[v][u]; if(k == INF){ printf("%d===>", v); return; } getPath(v, k); getPath(k, u); } int main() { scanf("%d%d", &n, &m); memset(map, INF, sizeof(map)); memset(path, INF, sizeof(path)); int i, j, a, b, c; for(i = 0; i < n; ++i) map[i][i] = 0; for(i = 0; i < m; ++i){ scanf("%d%d%d", &a, &b, &c); map[a][b] = c; } Floyd(n); for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) if(map[i][j] != INF){ printf("%d->%d:%d the path is:", i, j, map[i][j]); getPath(i, j); printf("%d ", j); } return 0; }
BellmanFord:
题目描述
有向图负权的单源点最短路问题（BellmanFord 算法），如果最短路径有多条,输出路径经过边数较小的解; 如果最短路径边数相同,输出编号较小的序列.
输入
第1行：2个空格分开的整数n(2<=n<=500)和m(10<=m<=20000)，分别表示图的顶点数和边数。
第2..m+1行：每行3个空格分开的整数i，j， w。i表示一条边的起点，j表示终点， w表示权值。
第m＋2行：2个整数s，t(1<=s，t<=n),表示指定的顶点。
输出
第1行：最小距离
第2行：最短路径（从起点到终点的序列，用1个空格分开）
如果出现负权回路,输出:No Solution
| 样例输入 | 样例输出 |
| 6 7 1 2 2 1 3 -1 2 4 -3 3 4 3 3 6 7 4 6 -2 3 5 6 1 6 |
-3 1 2 4 6 |
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int f[20005][3],dis[505],s[505]; void print(int x) { if(s[x]==0) return; print(s[x]); printf(" %d",x); } int main() { int n,m,i,j,q,z; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d%d",&f[i][0],&f[i][1],&f[i][2]); scanf("%d%d",&q,&z); memset(dis,1,sizeof(dis)); dis[q]=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(dis[f[j][0]]+f[j][2]<dis[f[j][1]]&&i<n){ dis[f[j][1]]=dis[f[j][0]]+f[j][2]; s[f[j][1]]=f[j][0]; } if(i==n&&dis[f[j][0]]+f[j][2]<dis[f[j][1]]){ printf("No Solution"); return 0; } } } printf("%d ",dis[z]); printf("%d",q); print(z); }
Time：2017-02-03