hdu 2923 Einbahnstrasse

点击打开链接hdu 2923

思路：最短路+SPFA / 最短路+floyd

分析：
1 题目要求的是有n个点，然后有c个破车，这个c个破车可能在同一城市里面，现在要把这些破车统一拉到中心点1.
2 这题的中心在1点，那么所求 ans = 1->所有破车的距离之和 + 所有破车->1的之和。所以这里涉及到1->所有破车的距离 和 所有破车->1的距离，那么我们可以使用SPFA和floyd。如果使用的是floyd那么最后的ans = dis[1][i]+dis[i][1]；如果是SPFA就要先求一下1->所有破车的距离之和，然后在重新建图就是把边反向然后对1点SPFA ，在加上1->所有破车的和即可。
4  点的表示，利用map映射。
3  这一题给的n虽然才100，但是利用SPFA的时候要数组记得开1010，因为c最大为1000.这个地方杭电是WA，不给RE，所以我WA了40+。


代码：

/*floyd*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF

int n , m , r , cnt;
int value[MAXN][MAXN];
int num[1010];
char ch[1010][20];
map<string , int>mp;

void init(){
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= n ; j++)
          value[i][j] = INF;
       value[i][i] = 0;
    }
}

void input(){
    int a , b , v;
    cnt = 0;
    char str1[MAXN] , str2[MAXN] , ch1 , ch2;
    mp.clear();
    for(int i = 1 ; i <= m+1 ; i++){
       scanf("%s" , ch[i]);
       a = mp[ch[i]];
       if(!a)
         a = mp[ch[i]] = ++cnt;
       num[i] = a;
    }
    for(int i = 0 ; i < r ; i++){
       scanf("%s" , str1);
       while((ch1 = getchar()) == ' ');
       scanf("-%d-%c %s" , &v , &ch2 , str2);
       a = mp[str1];
       b = mp[str2];
       if(!a)
         a = mp[str1] = ++cnt;
       if(!b)
         b = mp[str2] = ++cnt;
       if(ch1 == '<' && ch2 == '>'){
          if(value[a][b] > v)
             value[a][b] = v;
          if(value[b][a] > v)
             value[b][a] = v;
       }
       else if(ch1 == '<' && ch2 == '-'){
          if(value[b][a] > v)
             value[b][a] = v;
       }
       else{
          if(value[a][b] > v)
            value[a][b] = v;
       }
    }
}

void floyd(){
   for(int k = 1 ; k <= n ; k++){
      for(int i = 1 ; i <= n ; i++){
         for(int j = 1 ; j <= n ; j++){
            if(value[i][j] > value[i][k] + value[k][j])
              value[i][j] = value[i][k] + value[k][j];
         }
      }
   }
}

int main(){
   int ans , Case = 1;
   while(scanf("%d%d%d" , &n , &m , &r) && n+m+r){
     init();
     input();
     floyd();
     ans = 0;
     for(int i = 2 ; i <= m+1 ; i++)
        ans += value[1][num[i]] + value[num[i]][1];
     printf("%d. %d\n" , Case++ , ans);
   }
   return 0;
}

/*SPFA*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
#define MAXN 1010
#define INF 0xFFFFFFF

int n , m , r , cnt;
int value[MAXN][MAXN];
int tmpValue[MAXN][MAXN];
char ch[MAXN][20];
int dis[MAXN];
int vis[MAXN];
int num[MAXN];
queue<int>q;
map<string , int>mp;

void init(){
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= n ; j++)
            value[i][j] = INF;
       value[i][i] = 0;
    }
}

void input(){
    int a , b , v;
    cnt = 0;
    char str1[MAXN] , str2[MAXN] , ch1 , ch2;
    mp.clear();
    for(int i = 1 ; i <= m+1 ; i++){
       scanf("%s" , ch[i]);
       a = mp[ch[i]];
       if(!a)
         a = mp[ch[i]] = ++cnt;
       num[i] = a;
    }
    for(int i = 0 ; i < r ; i++){
       scanf("%s" , str1);
       while((ch1 = getchar()) == ' ');
       scanf("-%d-%c %s" , &v , &ch2 , str2);
       a = mp[str1];
       b = mp[str2];
       if(!a)
         a = mp[str1] = ++cnt;
       if(!b)
         b = mp[str2] = ++cnt;
       if(ch1 == '<' && ch2 == '>'){
          if(value[a][b] > v)
             value[a][b] = v;
          if(value[b][a] > v)
             value[b][a] = v;
       }
       else if(ch1 == '<' && ch2 == '-'){
          if(value[b][a] > v)
             value[b][a] = v;
       }
       else{
          if(value[a][b] > v)
            value[a][b] = v;
       }
    }
}

/*重新建图*/
void rebuild(){
    memcpy(tmpValue , value , sizeof(value));
    init();
    for(int i = 1 ; i <= cnt ; i++){
       for(int j = 1 ; j <= cnt ; j++){
          if(tmpValue[i][j]){
            value[j][i] = tmpValue[i][j]; 
          }
       }
    }
}

/*SPFA算法*/
void SPFA(){
   memset(vis , 0 , sizeof(vis));
   for(int i = 2 ; i <= cnt ; i++)
      dis[i] = INF; 
   dis[1] = 0;
   vis[1] = 1;
   q.push(1);
   while(!q.empty()){
      int x = q.front();
      q.pop();
      vis[x] = 0;
      for(int i = 1 ; i <= cnt ; i++){
         if(value[x][i] && dis[i] > dis[x] + value[x][i]){
           dis[i] = dis[x] + value[x][i];
           if(!vis[i]){
              vis[i] = 1;
              q.push(i);
           }
         }
      }
   }
}


int main(){
   int ans , Case = 1;
   while(scanf("%d%d%d" , &n , &m , &r) && n+m+r){
       init();
       input();

       SPFA();/*第一次SPFA*/
       ans = 0;
       for(int i = 2 ; i <= m+1 ; i++)
          ans += dis[num[i]];

       rebuild();/*图重建*/
       SPFA();/*第二次SPFA*/
       for(int i = 2 ; i <= m+1 ; i++)
          ans += dis[num[i]];

       printf("%d. %d\n" , Case++ , ans);
   }
   return 0;
}