ACM集训队个人赛5 I 题题解

原题链接:xinz

描述

crq没钱出去玩,只好自己虚拟旅行,它找了很多很多的地名(都是A~J开头,太多找不动了),想要从任意一个A开头的地名,再去一个B开头的地名,以此类推,直到J开头的地名结束旅行(中间没有重复且不漏,即不会有两个地名的第一个字母相同,也不会缺掉某个字母开头)。

crq查了几条路线,给每条路标记了花费,他想知道花费最少的一条路线。

输入

第一行为数据组数t,接下来有t组数据。

每组数据的第一行为n(10<=n<=105)和m(9<=m<=106),表示地名数量和道路条数。

接下来n行,每行一个字符串表示地名(都是大写字母A~J开头,后面都是小写字母,长度不超过10)。

接下来有m行,每行为两个字符串u和v,一个整数w,其中u和v为地名(在给定列表中),w为u到v的花费(1<=w<=1000),路线是双向的且来回的花费相同。

数据保证一定存在一条路线。

注意:crq可以经过某个城市不玩,比如A到C有路,且C到B有路,crq也可以A到B。

输出

每组在一行中输出花费最少的一条路线所需的花费值。

样例输入

1
11 10
Anhui
Anqing
Beijing
Chongqing
Denghuang
Europe
Fuzhou
Guangzhou
Hangzhou
Italy
Jiaojiang
Anhui Jiaojiang 1
Jiaojiang Anqing 2
Italy Jiaojiang 1
Guangzhou Italy 1
Hangzhou Guangzhou 1
Fuzhou Hangzhou 1
Europe Fuzhou 1
Europe Denghuang 1
Denghuang Chongqing 1
Beijing Chongqing 1

样例输出

19

题解

  • 如题所示crq必须先到 A 旅行,在到 B 旅行,再到 C 旅行.....最后再J城结束旅行。又因为可以经过这个城市不玩,所以我们可以通过经过其他城市来到达想要去的城市。
  • 很明显这个图是一个分层图,我们可以将最后已经到达的城市进行分层( 比如说 crq现在在首字母为 C 的城市,但是,他没有经过 B 城市,所以这一层应该是为第一层,然后他将要去首字母为 B 城市,那么这一层就转换成了第二层)之后我们建立一个超级源点和一个超级汇点,对每个 A 城市与 0 号点建边,每个 J 城市与 n+1 号点建边,最后只要输出 n+1 号点的第 10 层(依次递推 J 应为 10 )即为答案
  • 分层图不熟悉的可以看 拯救大兵瑞典 链接 :xinz

最终AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
const int N=1e5+5,M=4e6+5;//因为要与超级源点与超级汇点建边,所以 M 的值要大一点
typedef long long ll;
map<string,int>mp;//城市的编号
int op[N];//城市的首字母
int h[N],ne[M],w[M],e[M],idx;
int n,m;
ll f[N][12];
bool st[N][12];
void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;
    ne[idx]=h[a];h[a]=idx++;
}
struct aa{
    int x,y;
};
ll spfa(){
    memset(f,0x3f,sizeof(f));
    queue<aa>que;
    que.push({0,0});
    st[0][0]=1;f[0][0]=0;
    while(que.size()){
        aa b=que.front();que.pop();
        st[b.x][b.y]=0;
        int u=b.x;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i],t=b.y;
            if(t+1==op[j])t++;//假如说要去的城市与下一层相同,则层数加一
            if(f[j][t]>f[u][b.y]+w[i]){
                f[j][t]=f[u][b.y]+w[i];
                if(!st[j][t])que.push({j,t}),st[j][t]=1;
            }
        }
    }
    return f[n+1][10];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        memset(h,-1,sizeof(h));
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            string s;
            cin>>s;
            mp[s]=i;
            op[i]=s[0]-'A'+1;//第 i 个城市的首字母是什么
            if(s[0]=='A')add(0,i,0);
            else if(s[0]=='J')add(i,n+1,0);
        }
        while(m--){
            string s1,s2;
            int c;
            cin>>s1>>s2>>c;
            int a=mp[s1],b=mp[s2];
            add(a,b,c);add(b,a,c);
        }
        cout<<spfa()<<endl;
    }
    return 0;
}
上一篇:二、.Net Core 依赖注入详解及Autofac使用(DI推荐实践方式)


下一篇:依赖注入框架(DI Framework)