社区讨论
求帮助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 条回复,欢迎继续交流。
正在加载回复...