题解：SP4555 ANARC08F - Einbahnstrasse

一道多源最短路问题，肯定用 Floyd，还有个问题就是怎么处理输入。

使用 sscanf(edge+2,"%d",&cost); 从 edge 的第三个字符开始读取边权，然后处理左右两侧的箭头即可。

#include<bits/stdc++.h>
using namespace std;

map<string,int>cn;
int ct;
int q[1028];
int add_city(const char *name){
	int &x=cn[name];
	if(!x)x=ct++;
	return x;
}
int main(){
	int N,C,R;
	int MAT[121][121];
	int t=1;
	while(114514<1919810){
		scanf("%d%d%d",&N,&C,&R);
		if(!N) break;
		int i,j;
		cn.clear();
		memset(MAT,0x3f,sizeof MAT); 
		ct=1;
		char Garage[11];
		char CarLoc[1010][12];
		cn[Garage]=ct;
		ct++;
		++C;
		char c1[11],c2[11],edge[11];
		for(i=0;i<C;i++){
			scanf("%s",c1);
			q[i]=add_city(c1);
		}
		int cost;
		int a,b;
		for(i=0;i<R;i++){
			scanf("%s%s%s",c1,edge,c2);
			sscanf(edge+2,"%d",&cost);
			a=add_city(c1);
			b=add_city(c2);
			int len=strlen(edge);
			if(edge[0]=='<')
				MAT[b][a]=min(cost,MAT[b][a]);
			if(edge[len-1]=='>')
				MAT[a][b]=min(cost,MAT[a][b]);
		}
		int k;
		for(k=1;k<ct;k++)
			for(i=1;i<ct;i++)
				for(j=1;j<ct;j++)
					if(MAT[i][k]+MAT[k][j]<MAT[i][j])
						MAT[i][j]=MAT[i][k]+MAT[k][j];
		int ans=0,origin=q[0];
		for(i=1;i<C;i++)
			ans=ans+MAT[origin][q[i]]+MAT[q[i]][origin];
		printf("%d. %d\n",t,ans);
		t++;
	}
	return 0;
}