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 ",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 ",cnt++); printf("Frog Distance = %.3f ",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: ",k); printf("%d ",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 "); else printf("NO "); } }
POJ1502 MPI Maelstrom
题意：
由于叛徒朱子明的出卖，导致独立团在赵家峪的团部驻军在团长李云龙大婚之日几乎全军覆没，突出重围之后，李云龙决定集合所有驻扎在外的部队，使用重型武器意大利炮攻打平安县城，消息从团部传出之后到达各部驻地之后，驻地长官会派出自己的通讯人员通知其他驻地部队，自团部派人传达命令开始，至少经过多长时间才能使得所有驻扎在外的部队受到命令。（假设通讯员在路上不会遭遇任何意外）
题解：
floyd做
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxn=105; const int inf=1e9; int g[maxn][maxn]; int N; int getDis (string s) { if (s=="x") return inf; int ans=0; for (int i=0;i<s.length();i++) ans=ans*10+s[i]-'0'; return ans; } string s; void floyd () { for (int k=1;k<=N;k++) for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) if (i!=j) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } int main () { scanf("%d",&N); for (int i=1;i<N;i++) { for (int j=1;j<=i;j++) { cin>>s; g[i+1][j]=g[j][i+1]=getDis(s); } } floyd(); int ans=-1; for (int i=1;i<=N;i++) ans=max(ans,g[1][i]); printf("%d ",ans); }
POJ3660 Cow Contest
题意：
FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。
题解：
floyd做，对于一个节点，当肯定比它小的数量和肯定比它大的数量等于N-1时，就可以确定排名
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int maxn=105; const int inf=1e9; int g[maxn][maxn]; int N,M; void floyd () { for (int k=1;k<=N;k++) for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) if (i!=j) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } int l[maxn],r[maxn]; int main () { scanf("%d%d",&N,&M); 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; scanf("%d%d",&u,&v); g[u][v]=1; } floyd(); for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) if (i!=j&&g[i][j]!=inf) l[i]++,r[j]++; int ans=0; for (int i=1;i<=N;i++) if (l[i]+r[i]==N-1) ans++; printf("%d ",ans); }
POJ1511 Invitation Cards
题意：
n-1个人从1号点出发，到剩余n-1个宣传点，然后再回到1号点汇报结果，求所有人往返路径和的最小值
题解：
正反向建图，跑堆优化的dijkstra算法
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int maxn=1e6+10; const ll inf=1e18; struct node { int u,v,w,next; }edge[maxn*2]; 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++; } ll d[maxn]; int visit[maxn]; int N,M; struct qnode { int v,w; bool operator < (const qnode &r) const { return w>r.w; } }; void dijkstra (int s) { memset(visit,0,sizeof(visit)); fill(d,d+maxn,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); } } } } struct e { int u,v,w; }tt[maxn]; int main () { int T; scanf("%d",&T); while (T--) { memset(head,-1,sizeof(head)); tol=0; scanf("%d%d",&N,&M); for (int i=0;i<M;i++) scanf("%d%d%d",&tt[i].u,&tt[i].v,&tt[i].w); for (int i=0;i<M;i++) addedge(tt[i].u,tt[i].v,tt[i].w); dijkstra(1); ll ans=0; for (int i=1;i<=N;i++) ans+=d[i]; tol=0; memset(head,-1,sizeof(head)); for (int i=0;i<M;i++) addedge(tt[i].v,tt[i].u,tt[i].w); dijkstra(1); for (int i=1;i<=N;i++) ans+=d[i]; printf("%lld ",ans); } }
POJ3159 Candies
题意：
在幼儿园的时候，Flymouse是班上的班长。有时班主任会给班上的孩子们带来一大袋糖果，让他们分发。所有的孩子都非常喜欢糖果，经常比较他们和别人买的糖果的数量。一个孩子A可以有这样的想法，尽管可能是另一个孩子B在某些方面比他好，因此他有理由比他应得更多的糖果，但无论他实际得到多少糖果，他都不应该得到比B少的一定数量的糖果，否则他会感到不满意。 Flymouse总是把他的糖果和snoopy的比较，他想在让每个孩子都满意的同时，尽可能使自己的糖比snoopy的多。现在他又从班主任那里得到了一袋糖果，他最多能比snoopy多拿到几颗糖？
题解：
差分约束，对每个关系建一条单向边，跑1到N的最短路，堆优化的dijkstra算法
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int maxn=3e5+100; const int inf=1e9; int N,M; struct node { int u,v,w,next; }edge[maxn*2]; int head[maxn*2]; 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)); fill(d,d+maxn,inf); priority_queue<qnode> q; d[s]=0; 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; 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 () { scanf("%d%d",&N,&M); 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); } dijkstra(1); printf("%d",d[N]); return 0; }
HDU4725 最短路分层
题意：
给出一张无向图，和每个节点所在的层数，相邻层的节点之间可以通过固定的代价抵达，询问1到N的最短路径。
题解：
暴力建图肯定会爆栈，考虑拆点，每个层拆出一个中间点，所在层对应的中间点向每个点建单向边，每个点向上下相邻层的中间点建双向边。
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<vector> using namespace std; const int maxn=7e5+100; const int inf=1e9; struct node { int u,v,w,next; }edge[maxn*2]; int head[maxn*2]; int tol; 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++; } struct qnode { int v,w; bool operator < (const qnode &r) const { return w>r.w; } }; int d[maxn]; int visit[maxn]; void dijkstra (int s) { fill(visit,visit+maxn,0); fill(d,d+maxn,inf); d[s]=0; priority_queue<qnode> q; q.push({s,d[s]}); while (!q.empty()) { qnode now=q.top(); q.pop(); int u=now.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[u]+edge[i].w<d[v]) { d[v]=d[u]+edge[i].w; q.push({v,d[v]}); } } } } int main () { int T; scanf("%d",&T); for (int k=1;k<=T;k++) { int N,M,C; scanf("%d%d%d",&N,&M,&C); memset(head,-1,sizeof(head)); tol=0; for (int i=1;i<=N;i++) { int x; scanf("%d",&x); addedge(N+x,i,0); addedge(i,N+x+1,C); addedge(N+x+1,i,C); if (x>1) { addedge(i,N+x-1,C); addedge(N+x-1,i,C); } } 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); if (d[N]==inf) d[N]=-1; printf("Case #%d: %d ",k,d[N]); } }