2022河南萌新联赛第（三）场：河南大学 I - 旅行

I - 旅行

题意：从城市 1 到城市 n, 每隔一天多花费 w。
解法：将每个城市看成两个城市, 缴费的, 未缴费的, 然后让缴费于未缴费的城市建边, 跑最短路即可。

• 时间复杂度 $O(n\times log(n))$

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,PII> PLII;
const int N = 100010;

vector<PII> g[N];
bool st[N][2];
LL d[N][2];
int n,m,x;

void dijkstra()
{
    
	memset(d,0x3f,sizeof d);
	priority_queue<PLII,vector<PLII>,greater<PLII> > Q;//Q.first -> d, Q.second.first -> didian, Q.second.second -> hesuan
	d[1][0]=0;
	Q.push({
    0,{
    1,0}});
	while(!Q.empty())
	{
    
		auto t=Q.top();Q.pop();
		int u=t.second.first,ok=t.second.second;
		if(st[u][ok]) continue;
		st[u][ok]=true;
		for(auto &p:g[u])
		{
    
			int j=p.first,w=p.second;
			if(ok==1 && d[j][0]>d[u][1]+w) // 0 -> 1
			{
    
				d[j][0]=d[u][1]+w;
				Q.push({
    d[j][0],{
    j,0}});
			}
			if(ok==0 && d[j][1]>d[u][0]+w+x)// 1 -> 0, + x;
			{
    
				d[j][1]=d[u][0]+w+x;
				Q.push({
    d[j][1],{
    j,1}});
			}
		}
	}
}

int main()
{
    
	cin>>n>>m>>x;
	for(int i=1;i<=m;i++)
	{
    
		int u,v,w;cin>>u>>v>>w;
		g[u].push_back({
    v,w});
		g[v].push_back({
    u,w});
	}
	dijkstra();
	cout<<min(d[n][0],d[n][1])<<endl;
	return 0;
}