HDU 2923 Einbahnstrasse(dijkstra)

#include <bits/stdc++.h>
#define maxn 105
#define maxm 10005
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
  int to,w,next;
  bool operator < (const Node &a) const{
    return a.w < w;
  }
}Edge[maxm << 1],Now,Next;
struct b{
  int u,v,w;
}b[maxm << 1];
int head[maxn << 1],num,dist[maxn << 1];
int n,c,r;

void init(){
  memset(head,-1,sizeof(head));
  num = 0;
}

void add(int u,int v,int w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].next = head[u];
  head[u] = num ++;
}

int toInt(string s){
  string str;
  int len = s.length();
  for(int i=0;i<len;i++){
    if(s[i] >= '0' && s[i] <= '9'){
      str += s[i];
    }
  }
  int ans = atoi(str.c_str());
  return ans;
}

void dijkstra(int s){
	bool vis[maxn << 1];
	memset(vis,false,sizeof(vis));
	memset(dist,inf,sizeof(dist));
	dist[s] = 0;
	Now.to = s;
	priority_queue<Node> q;
	q.push(Now);
	while(!q.empty()){
		Now = q.top();
		q.pop();
		int ans = Now.to;
		if(vis[ans]) continue;
		vis[ans] = true;
		for(int i=head[ans];i!=-1;i=Edge[i].next){
			int u = Edge[i].to;
			if(!vis[u] && dist[u] > dist[ans] + Edge[i].w){
				dist[u] = dist[ans] + Edge[i].w;
				Next.to = u;
				Next.w = dist[u];
				q.push(Next);
			}
		}
	}
}

int main()
{
  int Case = 1;
  while(~scanf("%d%d%d",&n,&c,&r)){
    if(n == 0 && c == 0 && r == 0) break;
    map<string,int> ma;
    vector<string> v(maxm);
    c ++;
    for(int i=0;i<c;i++){
      cin>>v[i];
    }
    int xx = 1;
    int cnt = 0;
    string str1,str2,str3;
    for(int i=0;i<r;i++){
      cin>>str1>>str2>>str3;
      int w = toInt(str2);
      if(ma[str1] == 0) ma[str1] = xx ++;
      if(ma[str3] == 0) ma[str3] = xx ++;
      if(str2[0] == '<'){
        b[cnt].u = ma[str3];
        b[cnt].v = ma[str1];
        b[cnt++].w = w;
      }
      if(str2[str2.length() - 1] == '>'){
        b[cnt].u = ma[str1];
        b[cnt].v = ma[str3];
        b[cnt++].w = w;
      }
    }
    int ans = 0;
    init();
    for(int i=0;i<cnt;i++){
      add(b[i].u, b[i].v, b[i].w);
    }
    dijkstra(ma[v[0]]);
    for(int i=0;i<c;i++){
      ans += dist[ma[v[i]]];
    }
    init();
    for(int i=0;i<cnt;i++){
      add(b[i].v, b[i].u, b[i].w);
    }
    dijkstra(ma[v[0]]);
    for(int i=0;i<c;i++){
      ans += dist[ma[v[i]]];
    }
    printf("%d. %d\n",Case++,ans);
  }
  return 0;
}