练习40，小蓝的旅行【最短路】_小蓝的旅行计划 最短路经

小蓝的旅行 (nowcoder.com)

根据题意，我们知道只能从未做核酸的城市到做核酸的城市或者从做核酸的城市到未做核酸的城市，所以我们可以将每个点分别当成未做核酸的和做了核酸的，然后分别建边求最短路

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define NOTLE ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define T int TT;cin >> TT;while (TT--)
#define lint long long
#define pb push_back
#define eb emplace_back
int last[800010],ne[800010],to[800010],w[800010],cnt=0; //要开4倍(无向图+是否做核酸
int n,m,x;
lint d[200010],vis[200010]={0};
void add(int a,int b,int c){ //链式前向星存图
    ne[++cnt]=last[a];
    to[cnt]=b;
    w[cnt]=c;
    last[a]=cnt;
}
 
void SPFA(){
    memset(d,INF,sizeof(d));
    queue<int> q;
    q.push(1);
    d[1]=0,vis[1]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=last[now];i;i=ne[i]){
            if(d[to[i]]>d[now]+w[i]){
                d[to[i]]=d[now]+w[i];
                if(!vis[to[i]]){
                    q.push(to[i]);
                    vis[to[i]]=1;
                }
            }
        }
    }
}
int main(){
    NOTLE;
    cin >> n >> m >> x;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        if(a==1){ //一开始是没有做核酸的
            add(a,b+n,c+x);
            add(b+n,a,c);
        }
        else{ //由于是无向图存两遍，而且要保证只能从有→无或无→有
            add(a+n,b,c);
            add(b,a+n,c+x);
            add(a,b+n,c+x);
            add(b+n,a,c);
        }
    }
    SPFA();
    cout << min(d[n],d[n+n]) << endl;
    return 0;
}