《算法周练3题解》 C

C：
分层图的最短路.
思路：
对于每一层里面的点建边.
然后给每个车站开一个虚点,和每个地铁里对应的车站建边。
这里的对应应该每次都要和对应地铁里建边。
建边:
对于每一层,最多的点数就是总车站数n。
所以给每一层开n个点存这一层的信息,可能会有空缺,但是没什么影响。
然后和前面的点建立双向边,因为地铁也可以往回坐.
边的权值是这一条线路坐一站的花费bi.
这里默认虚点为[1,n].
第一条地铁就是[1n+1,1n+n]
可以从图中理解下。
a1为坐地铁1的花费,b1为地铁1之间坐多一站的花费.
a,b2同理.

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e6+5;
const int M = 10000;
#define pi acos(-1)
#define INF 1e8
#define INM INT_MIN
#define pb(a)  push_back(a)
#define mk(a,b) make_pair(a,b)
#define dbg(x) cout << "now this num is " << x << endl;
#define met0(axx) memset(axx,0,sizeof(axx));
#define metf(axx) memset(axx,-1,sizeof(axx));
#define sd(ax) scanf("%d",&ax)
#define sld(ax) scanf("%lld",&ax)
#define sldd(ax,bx) scanf("%lld %lld",&ax,&bx)
#define sdd(ax,bx) scanf("%d %d",&ax,&bx)
#define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx)
#define sfd(ax) scanf("%lf",&ax)
#define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx)
#define pr(a) printf("%d\n",a)
#define plr(a) printf("%lld\n",a)    
int n,m,s,t,head[N],dis[N],cnt = 0;
struct Node{int to,next,dis;}e[N<<1];
void add(int u,int v,int w)
{
    e[++cnt].to = v,e[cnt].dis = w,e[cnt].next = head[u],head[u] = cnt;
}
void djst(int s)
{
    for(int i=1;i<=n*(m+1);++i) dis[i] = INF;//因为有虚点所以多了一个n的点.
    dis[s] = 0;
    priority_queue<pii,vector<pii>,greater<pii> >Q;
    Q.push(pii(0,s));
    while(!Q.empty())
    {
        int u = Q.top().second,d = Q.top().first;
        Q.pop();
        if(d > dis[u]) continue;
        for(int i=head[u];i;i=e[i].next)
        {
            int y = e[i].to;
            if(dis[y] > dis[u]+e[i].dis)
            {
                dis[y] = dis[u]+e[i].dis;
                Q.push(pii(dis[y],y));
            }
        }
    }
}
int main()
{
    sdd(n,m);sdd(s,t);
    for(int i=1;i<=m;++i)
    {
        int a,b,c;sddd(a,b,c);
        int pre = -1;
        while(c--)
        {
            int x;sd(x);
            if(pre != -1)
            {
                add(i*n+x,i*n+pre,b);
                add(i*n+pre,i*n+x,b);
            }
            pre = x;
            add(x,i*n+x,a);add(i*n+x,x,0);//和虚点建边,注意去地铁是花费a,到虚点车站不需要花费.所以是0
        }
    }
    djst(s);
    if(dis[t] == INF) printf("-1\n");
    else pr(dis[t]);
    system("pause");
    return 0;
}