自动搬运

查看原文

来自洛谷，原作者为

	Strelizia_Qy 「お前の人生歪める権利を俺にくれ」

搬运于2025-08-24 22:42:37，当前版本为作者最后更新于2022-12-19 15:57:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Dijkstra 堆优化 + vector 存图

看到各位 dalao 都用链式前向星，奈何我不会，所以写一篇用 vector 存的。

思路：

注意到是单源最短路，且没有负边权，选择 Dijkstra。

隔离的时间可以丢进路线的时间里，具体操作如下：

每条路的边权=原来的边权+目的地的点权。

这样就转化成了一个 Dijkstra 板子题。

（温馨提示：因为目的地不需要隔离，所以输出时减去城市 N 的隔离时间）

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int maxn=1e5+5,inf=0x3f3f3f3f;
int n,m,add[maxn],dis[maxn];
bool vis[maxn]={0};
vector<pii> G[maxn];
void dijkstra()//Dijkstra 
{
	for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
	dis[1]=0;
	priority_queue<pii,vector<pii>,greater<pii> >p;//堆优化 
	p.push({0,1});
	while(!p.empty())
	{
		int u=p.top().second;
		p.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++)
		{
			int cost=G[u][i].second,v=G[u][i].first;
			if(dis[v]>dis[u]+cost)
			{
				dis[v]=dis[u]+cost;
				p.push({dis[v],v});
			}
		} 
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>add[i];
	for(int i=1;i<=m;i++)
	{
		int a,b,len;
		cin>>a>>b>>len;
		G[a].push_back({b,len+add[b]});
		G[b].push_back({a,len+add[a]});
		//vector存图，加上目的地点权 
	}
	dijkstra();
	cout<<dis[n]-add[n];//终点不用隔离 
}