首页 > 代码库 > POJ-1847 最短路裸题,Floyd, Bellman, Dijkstra, Spfa
POJ-1847 最短路裸题,Floyd, Bellman, Dijkstra, Spfa
POJ 1847
题意:n个点,电车从A到B。每个点可以到其它ki个点,但默认只通往给出的第一个点,如果要到其它点,必须改变轨道方向一次。问A到B最少改变几次轨道方向。
总结:裸裸的最短路,所以,狠狠的把Floyd, Bellman, Dijkstra, Spfa都给撸了一遍。一个字,爽!
// POJ-1847 //#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<bitset> #include<vector> #include<set> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define F(i,a,b) for (int i=a;i<b;i++) #define FF(i,a,b) for (int i=a;i<=b;i++) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200; int n, A, B; int G[N][N]; void Floyd() //O(V^3),任意两点间 { FF(k,1,n) FF(i,1,n) FF(j,1,n) { G[i][j] = min( G[i][j], G[i][k]+G[k][j] ); } if(G[A][B]==INF) puts("-1"); else printf("%d\n", G[A][B]); } int Q[N*N], dis[N], vis[N]; //Q队列要多开 void Spfa() //O(kE),k<=2,改进的Bellman,单源,可有负权,可判负环,但感觉有时候有点玄 { mes(vis, 0); mes(dis, INF); int head=0, tail=1; Q[head]=A, dis[A]=0; while(head < tail) { int u=Q[head]; vis[u]=1; FF(i,1,n) { if(G[u][i]!=INF && dis[i]> dis[u]+G[u][i]) { //G[u][i]!=INF表示e(u,i)这条边存在,也可用个flag[][]数组标记它是否存在 dis[i]= dis[u]+G[u][i]; if(vis[i]==0) { //要判断,因为i这个点如果取过,有可能会再次取到它 vis[i]=1, Q[tail++]=i; } } } vis[u]=0, head++; //vis[u]还要变回0,所以可以重复取到这个点 } if(dis[B]==INF) puts("-1"); else printf("%d\n", dis[B]); } int tot; struct Edge { int u, v, w; } edge[N*N]; void Bellman() //O(V*E),单源,可有负权,可判负环,但效率非常低 { mes(dis, INF); dis[A]=0; while(true) { bool update = false; F(i,0,tot) { Edge e=edge[i]; if(dis[e.v]> dis[e.u]+e.w) { dis[e.v]= dis[e.u]+e.w; update=true; } } if(update==false) break; //如果不能再松驰就跳出 } if(dis[B]==INF) puts("-1"); else printf("%d\n", dis[B]); } int find_min() //找到dis(A, i)最小的点 { int minn=INF, pos=-1; FF(i,1,n) if(vis[i]==0 && dis[i]<minn) { pos=i, minn=dis[i]; } return pos; } void Dijkstra1() //单源,不能有负权,不优化O(V^2) { mes(vis, 0); mes(dis, INF); dis[A]=0; int p=find_min(); while(p!=-1) { vis[p]=1; FF(i,1,n) if(vis[i]==0 && dis[i]> dis[p]+G[p][i]) { dis[i]= dis[p]+G[p][i]; } p=find_min(); } if(dis[B]==INF) puts("-1"); else printf("%d\n", dis[B]); } struct Node { int d, id; bool friend operator < (const Node &a, const Node &b) { return a.d > b.d; } }; void Dijkstra() //优先队列优化O(Elog(V)) { mes(vis, 0); mes(dis, INF); dis[A]=0; priority_queue<Node > PQ; PQ.push( (Node){0, A} ); while(!PQ.empty()) { Node pos=PQ.top(); PQ.pop(); if(vis[pos.id]==1) continue; //有可能被压入多次,第一次是最小的,后面的就不用再重复计算了 vis[pos.id]=1; FF(i,1,n) if(vis[i]==0) { if(dis[i] > dis[pos.id]+G[pos.id][i]) { dis[i]= dis[pos.id]+G[pos.id][i]; PQ.push( (Node){dis[i], i} ); } } } if(dis[B]==INF) puts("-1"); else printf("%d\n", dis[B]); } int main() { int ki, c; mes(G, INF); tot=0; scanf("%d%d%d", &n, &A, &B); FF(i,1,n) { scanf("%d", &ki); FF(j,1,ki) { scanf("%d", &c); if(j==1) G[i][c]=0, edge[tot].w=0; else G[i][c]=1, edge[tot].w=1; edge[tot].u=i, edge[tot++].v=c; } } //Floyd(); //Spfa(); //Bellman(); //Dijkstra1(); Dijkstra(); return 0; }
POJ-1847 最短路裸题,Floyd, Bellman, Dijkstra, Spfa
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。