POJ2387 Til the Cows Come Home （最短路裸题）
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn=1010; const int inf=1e9; int N,M; int head[maxn*100]; int tol; struct node { int u,v,w,next; }edge[maxn*100]; void addedge (int u,int v,int w) { edge[tol].u=u; edge[tol].v=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol++; } int d[maxn]; int visit[maxn]; struct qnode { int v,w; bool operator < (const qnode &r) const { return w>r.w; } }; void dijkstra (int s) { memset(visit,0,sizeof(visit)); for (int i=1;i<=N;i++) d[i]=inf; priority_queue<qnode> q; d[s]=0; qnode tmp; tmp.v=s,tmp.w=0; q.push(tmp); while (!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if (visit[u]) continue; visit[u]=1; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if (!visit[v]&&d[v]>d[u]+edge[i].w) { d[v]=d[u]+edge[i].w; tmp.v=v; tmp.w=d[v]; q.push(tmp); } } } } int main () { while (~scanf("%d%d",&M,&N)) { memset(head,-1,sizeof(head)); tol=0; for (int i=0;i<M;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dijkstra(1); printf("%d\n",d[N]); } }
POJ2253 Frogger （Floyd算法找起点到终点所有路径中的最长边最小）
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int maxn=1050; const int inf=1e9; struct node { int x,y; }Node[maxn]; int N; double g[maxn][maxn]; double getDis (int i,int j) { double x=Node[i].x-Node[j].x; double y=Node[i].y-Node[j].y; return sqrt(x*x+y*y); } void floyd () { for (int k=1;k<=N;k++) for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) g[i][j]=min(g[i][j],max(g[i][k],g[k][j])); } int main () { int cnt=1; while (scanf("%d",&N)&&N) { for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) g[i][j]=inf; for (int i=1;i<=N;i++) scanf("%d%d",&Node[i].x,&Node[i].y); for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) g[i][j]=g[j][i]=min(getDis(i,j),g[i][j]); floyd(); printf("Scenario #%d\n",cnt++); printf("Frog Distance = %.3f\n\n",g[1][2]); } }
POJ1797 Heavy Transportation （堆优化的dijkstra算法找起点到终点的路径中边权的最小值最大）
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn=1e6+10; const int inf=1e9; int N,M; int T; struct node { int u,v,w,next; }edge[maxn]; int head[maxn]; int tol=0; void addedge (int u,int v,int w) { edge[tol].u=u; edge[tol].v=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol++; } int d[maxn];//保存源点到每个点路径上的边权最小值的最大解 int visit[maxn]; struct qnode { int v,w; bool operator < (const qnode &r) const { return w<r.w;//选出最小值里的最大值 } }; void dijkstra (int s) { memset(visit,0,sizeof(visit)); memset(d,0,sizeof(d)); priority_queue<qnode> q; d[s]=inf; qnode tmp; tmp.v=s,tmp.w=d[s]; q.push(tmp); while (!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if (visit[u]) continue; visit[u]=1; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; int w=min(d[u],edge[i].w); if (d[v]<w) { d[v]=w; tmp.v=v,tmp.w=d[v]; q.push(tmp); } } } } int main () { scanf("%d",&T); for (int k=1;k<=T;k++) { memset(head,-1,sizeof(head)); tol=0; scanf("%d%d",&N,&M); for (int i=1;i<=M;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dijkstra(1); printf("Scenario #%d:\n",k); printf("%d\n\n",d[N]); } }
POJ3268 Silver Cow Party
分别正向反向建图，求解X点到所有点的最短路和所有点到X点的最短路。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<queue> using namespace std; const int maxn=1010; const int inf=1e9; int N,M,X; int g[maxn][maxn]; int rg[maxn][maxn]; int d[maxn]; int rd[maxn]; int visit[maxn]; struct qnode { int v,w; bool operator < (const qnode &r) const { return w>r.w; } }; void dijkstra (int g[maxn][maxn],int d[maxn],int s) { fill(d,d+maxn,inf); fill(visit,visit+maxn,0); d[s]=0; priority_queue<qnode> q; qnode tmp; tmp.v=s,tmp.w=d[s]; q.push(tmp); while (!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if (visit[u]) continue; visit[u]=1; for (int v=1;v<=N;v++) { if (d[u]+g[u][v]<d[v]) { d[v]=d[u]+g[u][v]; tmp.v=v; tmp.w=d[v]; q.push(tmp); } } } } int main () { scanf("%d%d%d",&N,&M,&X); for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) g[i][j]=inf,rg[i][j]=inf; for (int i=0;i<M;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u][v]=w; rg[v][u]=w; } dijkstra(g,d,X); dijkstra(rg,rd,X); int ans=0; for (int i=1;i<=N;i++) ans=max(ans,d[i]+rd[i]); printf("%d",ans); }
POJ3259 Wormholes
题意：
教学楼里有很多教室，这些教室由双向走廊连接。另外，还存在一些单向的秘密通道，通过它们可以回到过去。现在有 N (1 ≤ N ≤ 500) 个教室，编号 1..N, M (1 ≤ M ≤ 2500) 条走廊，和 W (1 ≤ W ≤ 200) 条秘密通道。
DY在养猫之余，还是一个时间旅行爱好者。她希望从一间教室出发，经过一些走廊和秘密通道，回到她出发之前的某个时间。
共有F (1 ≤ F ≤ 5) 组数据。对每组数据，判断DY是否有回到过去的可能性。不存在耗时超过10,000秒的走廊，且不存在能带DY回到10,000秒之前的秘密通道。
题解：
floyd算法找负环
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=505; const int inf=1e9; int g[maxn][maxn]; int N,M,W; int floyd () { for (int k=1;k<=N;k++) for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { if (g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j]; } if (g[i][i]<0) return 1; } return 0; } int main () { int F; scanf("%d",&F); while (F--) { scanf("%d%d%d",&N,&M,&W); for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) g[i][j]=inf; for (int i=0;i<M;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u][v]=min(g[u][v],w); g[v][u]=g[u][v]; } for (int i=0;i<W;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u][v]=-w; } int ans=floyd(); if (ans) printf("YES\n"); else printf("NO\n"); } }
原文：https://www.cnblogs.com/zhanglichen/p/12597979.html
