学步园

思路：变异的dij 在松弛的地方要改一下，即当前点i的最大负载为min(dist[k], map[k][i]);这样就能保定
负载是这条线路上最小的；

//320K   
16MS

#include <stdio.h>
#include <string.h>
#define M 205
#define MAX 10005
const int inf = 10001;
char name[M][35];
int map[M][M];
int count,n,src,des;  //src是起点，des是终点
int min (int a,int b)
{
    return a
> b?b:a;
}
int find (char *p)  //给每个城市标号
{
    int i;
    for (i = 0;
i < count; i ++)
       
if (strcmp(p,name[i]) == 0)
           
return i;
    strcpy
(name[count++],p);
    return count
- 1;
}

void dij
()    
//很纯粹的dij算法 只是把 dist[i] < dist[k]+map[k][i]改为
{              
//dist[i] = min(dist[k],map[k][i])
    int
dist[M],vis[M];
    int
i,j,k,maxflow;
    memset
(dist,0,sizeof(dist));
    memset
(vis,0,sizeof(vis));
    for (i = 0;i
< n;i ++)
       
dist[i] = map[src][i];
    dist[src] =
inf;

    int m = n -
1;
    while (m
--)
    {
       
int max = 0;
       
for (i = 0;i < n;i ++)
           
if (!vis[i]&&dist[i]
> max)
           
{
               
k = i;
               
max = dist[i];
           
}
       
vis[k] = 1;
       
for (i = 0;i < n;i ++)
           
if
(map[k][i]&&!vis[i]&&dist[i]
< min (max,map[k][i]))
               
dist[i] = min (max,map[k][i]);
    }
    printf ("%d
tons\n\n",dist[des]);
}
int main ()
{
    int
m,i,j,v1,v2,w;
    char
s1[35],s2[35];
    int t =
1;
    while (scanf
("%d%d",&n,&m)&&n&&m)

    {
       
count = 0;
       
memset (name,'\0',sizeof(name));