首页 > 代码库 > hdu 2923
hdu 2923
最短路加字符串处理
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <cstring>#include <cstdlib>#include <map>using namespace std;#define N 2005#define INF 0x3f3f3f3f#define LL __int64#define INF 0x3f3f3f3fchar s1[20],s2[20],s3[20],s[1005][20];int ma[N][N],d[N],vis[N];void flody(int n){ int i , j, k; for(k = 1 ; k <= n ; k++) { for(i = 1 ; i <= n ; i++) { if(ma[i][k]!=INF) { for(j = 1 ; j<=n ; j++) if(ma[i][k]+ma[k][j]<ma[i][j]) ma[i][j] = ma[i][k]+ma[k][j]; } } }}int main(){ int n,i,j,k,c,r,num ,cas = 1; map<string,int>m; while(~scanf("%d %d %d",&n,&c,&r),n+c+r) { num = 1; m.clear(); for(i = 1 ; i <= c+1;i++) { scanf("%s",s[i]); if(!m[s[i]]) m[s[i]] = num++; } for(i = 1; i<= N ;i++) for(j = 1; j<= N ;j++) ma[i][j] = (i==j)?0:INF; for(i = 1; i<= r ; i++) { scanf("%s %s %s",s1,s2,s3); int ans = 0,len2 = strlen(s2),x,y; for(j = 0 ; j < len2 ; j++) if(s2[j]>=‘0‘&&s2[j]<=‘9‘) ans = ans*10+s2[j] - ‘0‘; if(!m[s1]) m[s1] = num++; if(!m[s3]) m[s3] = num++; x = m[s1]; y = m[s3]; if(s2[0]==‘<‘&&s2[len2-1]==‘>‘){ if(ma[x][y]>ans) ma[x][y] = ans; if(ma[y][x]>ans) ma[y][x] = ans; }else if(s2[0]==‘<‘){ if(ma[y][x]>ans) ma[y][x] = ans; }else if(ma[x][y]>ans) ma[x][y] = ans; } flody(num); int sum = 0,p; for(i = 2 ; i <=c+1;i++) sum+=ma[m[s[i]]][1]+ma[1][m[s[i]]]; printf("%d. %d\n",cas++,sum); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。