本文共 1347 字,大约阅读时间需要 4 分钟。
/**@Author: STZG*@Language: C++*/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#define DEBUGusing namespace std;typedef long long ll;const int N=10000;const double PI = acos(-1.0);const double EXP = 1E-8;const int INF = 0x3f3f3f3f;int t,n,c,r,m;char s1[100],s2[100],c1,c2;char str[1005][100];int a[105][105];int main(){#ifdef DEBUG freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T=0; while(scanf("%d%d%d",&n,&c,&r)!=EOF&&n+c+r){ map M; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=INF; } } for(int i=0;i<=c;i++){ scanf("%s",str[i]); } int cnt=0; for(int i=1;i<=r;i++){ scanf("%s %c-%d-%c %s",s1,&c1,&t,&c2,s2); if(!M[s1]) M[s1]=++cnt; if(!M[s2]) M[s2]=++cnt; int x=M[s1],y=M[s2]; if(c1=='<'&&a[y][x]>t) a[y][x]=t; if(c2=='>'&&a[x][y]>t) a[x][y]=t; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){// if(a[j][k]>a[j][i]+a[i][k])// a[j][k]=a[j][i]+a[i][k]; a[j][k]=min(a[j][k],a[j][i]+a[i][k]); } } } ll ans=0; for(int i=1;i<=c;i++){ ans+=a[M[str[0]]][M[str[i]]]+a[M[str[i]]][M[str[0]]]; } printf("%d. %lld\n",++T,ans); } //cout << "Hello world!" << endl; return 0;}
转载地址:http://ffzof.baihongyu.com/