最近学习最短路算法,发现这个题目基本上能用很多最短路方法解,于是贴出所有代码:spfa邻接矩阵、spfa--数组邻接表、dijikstra、floyd、bellman_ford
spfa--邻接矩阵版
// AC 176k 0ms #include<cstdio> #include<queue> #include<cstring> using namespace std; #define MAX 10//想不通的是本来这里我用10 去调试..可以提交的时候忘了改..也过了..无语 int N;//N个经纪人 int v[MAX][MAX];//邻接表v[i][j]表示i号经纪人人到j号经纪人的时间 int d[MAX];//d[i]表示源点(也就是每次起点)到i的最少时间 bool flag[MAX];//每次spfa 对于每一个点入队一次,标记入队 void Input() { int m,to,time;//每个人的m个朋友,以及用时 memset(v,0,sizeof(v)); for(int i=1;i<=N;i++) { scanf("%d",&m); while(m--) { scanf("%d%d",&to,&time); v[i][to]=time; } } } void spfa() { int i,j; int ans[MAX]; for(i=1;i<=N;i++) ans[i]=0; for(i=1;i<=N;i++)//1到N都spfa一次 { for(j=1;j<=N;j++) d[j]=1001,flag[j]=false;//这里之所以d[i]初始化为1001,是因为100个人,每个人传达10 应该不会超过1001 d[i]=0; flag[i]=true; queue<int> q; q.push(i); while(!q.empty()) { int u=q.front();q.pop(); for(j=1;j<=N;j++) if(v[u][j]!=0 && d[j]>d[u]+v[u][j])// && !flag[j]这里注意...不管j在不在队列,都要松弛一次 { d[j]=d[u]+v[u][j];//松弛 if(!flag[j]) { flag[j]=true;q.push(j); } } } for(j=1;j<=N;j++)//一次spfa之后 d[]最大的就是本次的i到所有点的最短用时,即最短路 ans[i]= ans[i]>d[j] ? ans[i]:d[j]; } int ANS1=1001,ANS2; for(i=1;i<=N;i++)//取每个起点的最短路中 最小的值 if(ANS1>ans[i]) ANS1=ans[i],ANS2=i; if(ANS1!=1001) printf("%d %d\n",ANS2,ANS1); } int main() { while(scanf("%d",&N),N) { Input(); spfa(); } return 0; }
spfa数组邻接表
// AC 180k 16ms #include<cstdio> #include<queue> using namespace std; #define MAX 1001 struct node { int to,time; int next; }edge[MAX*2]; int head[MAX]; int tol; void add(int st,int end,int time) { edge[tol].to=end; edge[tol].time=time; edge[tol].next=head[st]; head[st]=tol++; } int N; void init() { int i; for(i=1;i<=N;i++) head[i]=-1; tol=0; for(i=1;i<=N;i++) { int m,to,time; scanf("%d",&m); while(m--) { scanf("%d%d",&to,&time); add(i,to,time); } } } int d[MAX]; bool flag[MAX]; int spfa(int s) { int i; for(i=1;i<=N;i++) flag[i]=false, d[i]=10*MAX; d[s]=0; queue<int>q;q.push(s); while(!q.empty()) { int u=q.front();q.pop(); flag[u]=false; for(int j=head[u];j!=-1;j=edge[j].next) { int v=edge[j].to,w=edge[j].time; if(d[v]>d[u]+w) { d[v]=d[u]+w; if(!flag[v]) flag[v]=true,q.push(v); } } } int ans=0; for(i=1;i<=N;i++) if(d[i]>ans) ans=d[i]; return ans; } int main() { while(scanf("%d",&N),N) { init(); int ans=10*MAX,ans_start; for(int i=1;i<=N;i++) { int x=spfa(i); if(x<ans) ans=x,ans_start=i; } printf("%d %d\n",ans_start,ans); } return 0; }
floyd--不用说肯定是邻接矩阵:
// 168k 0ms #include<stdio.h> #define MAX 6 #define INF 1<<29 int N; int map[MAX][MAX]; void init() { int i,to,m,time; for(i=1;i<=N;i++) for(int j=1;j<=N;j++) map[i][j]=INF; for(i=1;i<=N;i++) { scanf("%d",&m); while(m--) { scanf("%d%d",&to,&time); map[i][to]=time; } } } void floyd() { int i,j,k; for(k=1;k<=N;k++) for(i=1;i<=N;i++) for(j=1;j<=N;j++) if(i!=j) map[i][j]=map[i][j]>map[i][k]+map[k][j] ? map[i][k]+map[k][j]:map[i][j]; int ans1,ans2=INF; for(i=1;i<=N;i++) { int max=0; for(j=1;j<=N;j++) if(i!=j && map[i][j]>max) max=map[i][j]; if(max<ans2) ans2=max,ans1=i; } printf("%d %d\n",ans1,ans2); } int main() { while(scanf("%d",&N),N) { init(); floyd(); } return 0; }
dijikstra-邻接矩阵
#include<stdio.h> #define MAX 100 int N; int map[MAX][MAX]; void init() { int i,j; for(i=1;i<=N;i++) for(j=1;j<=N;j++) map[i][j]=0; int m,to,time; for(i=1;i<=N;i++) { scanf("%d",&m); while(m--) { scanf("%d%d",&to,&time); map[i][to]=time; } } } int d[MAX]; bool flag[MAX]; int Dijkstra(int s) { int i,j; for(i=1;i<=N;i++) flag[i]=false,d[i]=1001; d[s]=0; for(i=1;i<=N;i++) { int u=0,max=1001; for(j=1;j<=N;j++) { if(!flag[j] && max>d[j]) u=j,max=d[j]; } if(u==0) break; flag[u]=true; for(j =1; j<=N;j++) if(map[u][j]!=0 && d[j]>d[u]+map[u][j]) d[j]=d[u]+map[u][j]; } int ans=0; for(i=1;i<=N;i++) ans=ans>d[i] ? ans:d[i]; return ans; } int main() { while(scanf("%d",&N),N) { init(); int ans1=1001,ans2; for(int i=1;i<=N;i++) { int x=Dijkstra(i); if(ans1>x) ans1=x,ans2=i; } printf("%d %d\n",ans2,ans1); } return 0; }
bellman_ford--结构体数组
//AC 168k 0ms #include<stdio.h> #define MAX 101 struct node { int st,end,time; }edge[MAX]; int tol; int N; void init() { int i; tol=0; int m,to,time; for(i=1;i<=N;i++) { scanf("%d",&m); while(m--) { scanf("%d%d",&to,&time); edge[tol].st=i,edge[tol].end=to,edge[tol++].time=time; } } } int d[MAX]; int Bellman_ford(int s) { int i; for(i=1;i<=N;i++) d[i]=1001; d[s]=0; for(i=1;i<N;i++) { for(int j=0;j<tol;j++) { int u=edge[j].st,v=edge[j].end,w=edge[j].time; d[v]=d[u]+w<d[v] ? d[u]+w:d[v];//松弛 } } int ans=0; for(i=1;i<=N;i++) ans=ans>d[i] ? ans:d[i]; return ans; } int main() { while(scanf("%d",&N),N) { init(); int ans1=1001,ans2; for(int i=1;i<=N;i++) { int x=Bellman_ford(i); if(ans1 > x) ans1=x,ans2=i; } printf("%d %d\n",ans2,ans1); } return 0; }