代码：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef char State[12];
const int VN = 105;
const int EN = 10105;
const int HashSize = 10003;
const int INF = 0x7fffffff;
int n,c,r;
int size;
int head[VN];
int car[VN*10];
int pos;
int w[VN][VN];
class Hash{
public:
void init(){
rear = 1;
memset(head, -1, sizeof(head));
}
int insert(State &s){
int h = hash(s);
int u = head[h];
while(u!=-1){
if(strcmp(st[u], s)==0) return u;
u = next[u];
}
strcpy(st[rear], s);
next[rear] = head[h];
head[h] = rear;
return rear++;
}
private:
int hash(char *p){
int sum=0;
while(*p){ sum = sum*131 + *p++; }
return (sum&0x7fffffff)%HashSize;
}
int rear;
int head[HashSize];
int next[VN];
State st[VN];
}hash;
inline void init(){
size=pos=0;
memset(head, -1, sizeof(head));
hash.init();
for(int i=0; i<=n; ++i){
w[i][i] = INF;
for(int j=i+1; j<=n; ++j)
w[i][j] = w[j][i] = INF;
}
}
inline void Floyd(){
for(int k=1; k<=n; ++k)
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j){
if(w[i][k]!=INF && w[k][j]!=INF)
w[i][j] = min(w[i][j],w[i][k]+w[k][j]);
}
}
int main(){
State name1, name2;
char str1[20];
int u,v,cost,cas=1;
while(scanf("%d%d%d",&n,&c,&r)&&n+c+r){
init();
scanf("%s",name1);
hash.insert(name1);
for(int i=0; i<c; ++i){
scanf("%s",name1);
car[pos++] = hash.insert(name1);
}
for(int i=0; i<r; ++i){
scanf("%s %s %s", name1, str1, name2);
u = hash.insert(name1), v = hash.insert(name2);
sscanf(str1+2, "%d", &cost);
if(str1[0]=='<'&&str1[strlen(str1)-1]=='>'){
if(w[u][v]>cost) w[u][v] = cost;
if(w[v][u]>cost) w[v][u] = cost;
}
else if(str1[0]=='-'&&str1[strlen(str1)-1]=='>'){
if(w[u][v]>cost) w[u][v] = cost;
}
else{
if(w[v][u]>cost)w[v][u] = cost;
}
}
Floyd();
int ans=0;
for(int i=0; i<pos; ++i){
ans += w [car[i]]+w[car[i]] ;
}
printf("%d. %d\n",cas++,ans);
}
return 0;
} |