最近学习最短路算法，发现这个题目基本上能用很多最短路方法解，于是贴出所有代码：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;
}