首页 > 代码库 > 最短路
最短路
dij矩阵表示
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int n,m,a[205][205],dis[205]; bool vis[205]; void dij(int beg) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[beg] = 0; for(int i = 0;i <= n;i++) { int k = -1,minn = INF; for(int j = 0;j < n;j++) { if(!vis[j] && dis[j] < minn) { minn = dis[j]; k = j; } } if(k == -1) break; vis[k] = 1; for(int j = 0;j < n;j++) { if(!vis[j] && dis[k]+a[k][j] < dis[j]) { dis[j] = dis[k]+a[k][j]; } } } } int main() { while(~scanf("%d%d",&n,&m)) { memset(a,0x3f,sizeof(a)); while(m--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(w < a[u][v]) a[u][v] = a[v][u] = w; } int x,y; scanf("%d%d",&x,&y); dij(x); if(dis[y] == INF) printf("-1\n"); else printf("%d\n",dis[y]); } return 0; } //HDU1874
dij优先队列
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<vector> #define INF 0x3f3f3f3f using namespace std; struct edge { int to,w; edge(int a,int b):to(a),w(b){}; friend bool operator <(edge X,edge Y) { return X.w > Y.w; } }; vector<edge> v[205]; int n,m,dis[205]; bool vis[205]; void dij(int beg) { priority_queue<edge> q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[beg] = 0; q.push(edge(beg,0)); while(!q.empty()) { int now = q.top().to; q.pop(); if(vis[now]) continue; vis[now] = 1; for(int i = 0;i < v[now].size();i++) { int tt = v[now][i].to,ww = v[now][i].w; if(!vis[tt] && dis[now]+ww < dis[tt]) { dis[tt] = dis[now]+ww; q.push(edge(tt,dis[tt])); } } } } int main() { while(~scanf("%d%d",&n,&m)) { for(int i = 0;i < n;i++) v[i].clear(); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); v[a].push_back(edge(b,c)); v[b].push_back(edge(a,c)); } int x,y; scanf("%d%d",&x,&y); dij(x); if(dis[y] == INF) printf("-1\n"); else printf("%d\n",dis[y]); } return 0; } //HDU1874
floyd
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int n,m,a[205][205]; void floyd() { for(int k = 0;k < n;k++) { for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) a[i][j] = min(a[i][j],a[i][k]+a[k][j]); } } } int main() { while(~scanf("%d%d",&n,&m)) { memset(a,0x3f,sizeof(a)); for(int i = 0;i < n;i++) a[i][i] = 0; while(m--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(a[u][v] > w) a[u][v] = a[v][u] = w; } floyd(); int x,y; scanf("%d%d",&x,&y); if(a[x][y] == INF) printf("-1\n"); else printf("%d\n",a[x][y]); } return 0; } //HDU1874
bennman_ford
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; struct edge { int u,v,w; }e[2005]; int n,m,dis[205]; void bellman_ford(int beg) { memset(dis,0x3f,sizeof(dis)); dis[beg] = 0; for(int i = 1;i < n;i++) { for(int j = 1;j <= m;j++) { if(dis[e[j].u] != INF && dis[e[j].v] > dis[e[j].u]+e[j].w) { dis[e[j].v] = dis[e[j].u]+e[j].w; } } } } int main() { while(~scanf("%d%d",&n,&m)) { m *= 2; for(int i = 1;i <= m;i += 2) { int a,b,c; scanf("%d%d%d",&a,&b,&c); e[i].u = a; e[i].v = b; e[i].w = c; e[i+1].u = b; e[i+1].v = a; e[i+1].w = c; } int x,y; scanf("%d%d",&x,&y); bellman_ford(x); if(dis[y] == INF) printf("-1\n"); else printf("%d\n",dis[y]); } return 0; } //HDU1874
spfa
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<vector> #define INF 0x3f3f3f3f using namespace std; struct edge { int to,w; edge(int a,int b):to(a),w(b){}; }; int n,m,dis[205],c[205],vis[205]; vector<edge> v[205]; int spfa(int beg) { queue<int> q; memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); dis[beg] = 0; q.push(beg); vis[beg] = 1; c[beg] = 1; while(!q.empty()) { int now = q.front(); q.pop(); vis[now] = 0; for(int i = 0;i < v[now].size();i++) { int xx = v[now][i].to,ww = v[now][i].w; if(dis[now]+ww < dis[xx]) { dis[xx] = dis[now]+ww; vis[xx] = 1; c[xx]++; q.push(xx); if(c[xx] > n) return 0; } } } return 1; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i = 0;i < n;i++) v[i].clear(); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); v[a].push_back(edge(b,c)); v[b].push_back(edge(a,c)); } int x,y; scanf("%d%d",&x,&y); spfa(x); if(dis[y] == INF) printf("-1\n"); else printf("%d\n",dis[y]); } return 0; } //HDU1874
分层图最短路dij优先队列
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<queue> #define INF 0x3f3f3f3f using namespace std; struct edge { int to,cost; edge(int a,int b):to(a),cost(b){}; friend bool operator>(edge x,edge y) { return x.cost > y.cost; } }; vector<edge> v[11005]; int n,m,k,a[1005][1005],dis[11005],vis[11005]; priority_queue< edge,vector<edge>,greater<edge> > q; int dij() { while(!q.empty()) q.pop(); memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[1] = 0; q.push(edge(1,0)); while(!q.empty()) { int now = q.top().to; if(now == (k+1)*n) return dis[(k+1)*n]; q.pop(); if(vis[now]) continue; vis[now] = 1; for(int i = 0;i < v[now].size();i++) { int xx = v[now][i].to,yy = v[now][i].cost; if(yy+dis[now] < dis[xx]) { dis[xx] = yy+dis[now]; q.push(edge(xx,dis[xx])); } } } } int main() { while(~scanf("%d%d%d",&n,&m,&k)) { for(int i = 1;i <= 11000;i++) v[i].clear(); memset(a,0x3f,sizeof(a)); for(int i = 1;i <= m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); a[u][v] = min(a[u][v],w); a[v][u] = min(a[v][u],w); } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(i == j || a[i][j] == INF) continue; for(int l = 0;l <= k;l++) { v[l*n+i].push_back(edge(l*n+j,a[i][j])); if(l != k) { v[l*n+i].push_back(edge((l+1)*n+j,0)); } } } } printf("%d\n",dij()); } return 0; } //XDOJ1078
最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。