题解 | #小雨坐地铁#

根本不需要分层图，其实是dijkstra模板题

思路

让我们求从 s 到 t 的最短路
关键点在于建边 有手就行

很简单一题，不废话了，代码如下

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3+10;

bool st[N];
int a[N];
int dist[N];
int g[N][N];
int n,m,s,t;

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;

    for(int i=0;i<n;i++) {
        int t=-1;
        for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;

        st[t]=true;
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    return dist[t]==0x3f3f3f3f?-1:dist[t];
}

int main(){
    cin>>n>>m>>s>>t;
    memset(g,0x3f,sizeof g);

    //  这里我以为会超时，结果并没有，数据有点水了
    while(m--){
        int p1,p2,num;
        cin>>p1>>p2>>num;
        for(int i=1;i<=num;i++) cin>>a[i];

         for(int i=1;i<=num;i++) for(int j=i+1;j<=num;j++){   // 建边
             int x=a[i],y=a[j];
             if(abs(i-j)==1) g[x][y]=g[y][x]=min(g[x][y],p1+p2);
             else g[x][y]=g[y][x]=min(g[x][y],p1+abs(i-j)*p2);
         } 
    }

    cout<<dijkstra()<<endl;

    return 0;
}