T446079 十年灯 讲解

· · 题解

T446079 十年灯 讲解

题目
考察内容：图论。

Task 1：

简述：在可以交换任意一个点的两条出边的权值无数次的情况下，求从 1 到 n 的最短路。

由于没有负环（负权都没有），每个点必然只到达一次，那么每次走的那条边必是那个点的出边中权值最小的那个边，那么可以把每个点的所有出边都设为最小值，这样结果是不变的。
最后跑一遍 dijkstra 就行了。

Task 2：

简述：在可以交换任意一个点的两条边的权值无数次的情况下，求从 1 到 n 的最短路。

我们很容易发现不管两个边有没有共点，我们都有办法使两条边交换。那么我们最后走的必是最短的 k 条边。

代码： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=4e5+5;
struct edge{
    int to,w;
    inl friend bool operator<(edge x,edge y){
        return x.w>y.w;
    }
};
int id,n,m,u[N],v[N],w[N],f[N],mnc[N];
vector<edge>g[N];
priority_queue<edge>pq;
priority_queue<int,vector<int>,greater<int> >p; 
bool vis[N];
inl void dijkstra(){
    f[1]=0;
    pq.push({1,0});
    while(!pq.empty()){
        int u=pq.top().to;
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto x:g[u]){
            int v=x.to,w=x.w;
            if(f[v]>f[u]+w){
                f[v]=f[u]+w;
                if(!vis[v]) pq.push({v,f[v]});
            }
        }
    }
}
signed main(){
    FAST;
    memset(f,0x3f,sizeof(f));
    memset(mnc,0x3f,sizeof(mnc));
    cin>>id>>n>>m;
    rep(i,1,m){
        cin>>u[i]>>v[i]>>w[i];
        if(id==1) mnc[u[i]]=min(mnc[u[i]],w[i]);
        if(id==2) p.push(w[i]);
    }
    rep(i,1,m){
        if(id==1) g[u[i]].push_back({v[i],mnc[u[i]]});
        if(id==2) g[u[i]].push_back({v[i],1});
    }
    dijkstra();
    if(id==1) cout<<f[n];
    else{
        int sum=0;
        rep(i,1,f[n]){
            sum+=p.top();
            p.pop();
        }
        cout<<sum;
    }
    return 0;
}