社区讨论

求帮助RE了

P8802[蓝桥杯 2022 国 B] 出差参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@m0bu6j04
此快照首次捕获于
2024/08/27 10:57
2 年前
此快照最后确认于
2025/11/04 22:19
4 个月前
查看原帖
C
#include<bits/stdc++.h>
using namespace std;
int n,m,c[100005],u,v,w;
struct data{int to,w;};
vector<data>h[1000005];
queue<int>Q;
int dis[100005];
bool fa[10005];
int main()
{
	cin>>n>>m;
	memset(dis,63,sizeof dis);
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		h[u].push_back((data){v,w+c[v]});
		h[v].push_back((data){u,w+c[u]});
	}
	Q.push(1);
	dis[1]=0;
	fa[1]=1;
	while(Q.size())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<=h[x].size();i++)
		{
			int to=h[x][i].to,w=h[x][i].w;
			if(dis[to]>dis[x]+w)
			{
				dis[to]=dis[x]+w;
				if(fa[to]==0)
				{
					Q.push(to);
					fa[to]=1;
				}
			}
		}
	}
	cout<<dis[n]-c[n];
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...