蓝桥杯2022年第十三届决赛真题-出差

解题思路:

基本上是裸的单源最短路

将隔离天数加入到行程花费时间当中,也就是从城市a到城市b需要花费a城市隔离天数加上a到b道路的天数
注意事项:

n可以等于1
从1城市出发不需要隔离
参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int w;
	int to;
	int next;
}mp[200005];
int head[10005];
priority_queue<pair<int,int> >q;
int cnt=0;
void add(int x,int y,int z)
{
	mp[++cnt].next=head[x];
	mp[cnt].to=y;
	mp[cnt].w=z;
	head[x]=cnt;
}
int dis[10005];
int v[10005];
int c[10005];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i];
		v[i]=0;
		dis[i]=1E9;
	}
	c[1]=0;//1城市不需要隔离
	for(int i=1;i<=m;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		add(a,b,w+c[a]);
		add(b,a,w+c[b]);
	}
	q.push(make_pair(0,1));
	dis[1]=0;
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(v[x])
		{
			continue;
		}
		v[x]=1;
		for(int i=head[x];i;i=mp[i].next)
		{
			int y=mp[i].to;
			if(mp[i].w+dis[x]<dis[y])
			{
				
				dis[y]=mp[i].w+dis[x];
				q.push(make_pair(-dis[y],y));
			}
		}
	}
	cout<<dis[n];
	return 0;
}