有向图 具体方向看箭头 从起点到指定城市拉破车，一个城市可能有多个破车，一次只能拉一辆破车 也就是到了指定地点后要回到起点
假如有100辆破车 但是只有一个城市有 就得在起点与这个城市间往返100次
所以要用s1记录
然后 貌似这题是有重边的....
sscanf(s4,"%d" ,&w) ; 这个是错的=.= 在这折腾了半天
Sample Input
4 2 5 //城市数 破车数 边数
NewTroy Midvale Metrodale //起点 + 有破车的城市
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
0 0 0
Sample Output
1. 80 //Case. sum
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <algorithm> 6 # include <cmath> 7 # include <map> 8 # define LL long long 9 using namespace std ; 10 11 const int MAXN = 110 ; 12 const int INF = 0x3f3f3f3f; 13 int dis[MAXN][MAXN]; 14 int n ; 15 map<string,int> mp ; 16 17 void floyed()//节点从1~n编号 18 { 19 int i,j,k; 20 for(k=1;k<=n;k++) 21 for(i=1;i<=n;i++) 22 for(j=1;j<=n;j++) 23 if(dis[i][k]+dis[k][j] < dis[i][j]) 24 dis[i][j]=dis[i][k]+dis[k][j]; 25 26 } 27 28 int main() 29 { 30 // freopen("in.txt","r",stdin) ; 31 int m , c ; 32 int Case = 0; 33 while (cin>>n>>c>>m) 34 { 35 if (n == 0 && c == 0 && m == 0) 36 break ; 37 Case++ ; 38 int i , j ; 39 for(i=1;i<=n;i++) 40 for(j=1;j<=n;j++) 41 { 42 if(i==j)dis[i][j]=0; 43 else dis[i][j]=INF; 44 } 45 mp.clear() ; 46 string s1[1100] ,s2,s3; 47 int l = 1 ; 48 for (i = 0 ; i <= c ; i++) //起点+ 有破车的城市 49 { 50 cin>>s1[i] ; 51 if (!mp[s1[i]]) 52 mp[s1[i]] = l++ ; 53 } 54 char s4[20] ; 55 56 int w ; 57 while(m--) 58 { 59 cin>>s2>>s4>>s3 ; 60 bool f1 = 0 ; 61 bool f2 = 0 ; 62 if (!mp[s2]) 63 mp[s2] = l++ ; 64 if (!mp[s3]) 65 mp[s3] = l++ ; 66 int len = strlen(s4) ; 67 if (s4[0] == '<') 68 f1 = 1 ; 69 if (s4[len-1] == '>') 70 f2 = 1 ; 71 sscanf(&s4[2],"%d" ,&w) ; 72 if (f1 && w < dis[mp[s3]][mp[s2]]) 73 dis[mp[s3]][mp[s2]] = w ; 74 if (f2 && w < dis[mp[s2]][mp[s3]]) 75 dis[mp[s2]][mp[s3]] = w ; 76 } 77 floyed() ; 78 int sum = 0 ; 79 for (i = 1 ; i <= c ; i++) 80 { 81 sum += dis[mp[s1[0]]][mp[s1[i]]] ; 82 sum += dis[mp[s1[i]]][mp[s1[0]]] ; 83 } 84 cout<<Case<<". "<<sum<<endl ; 85 86 } 87 return 0; 88 }