本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-25 17:50:55

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;
}