社区讨论
好难受啊,求助大佬,改了一年
学术版参与者 4已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi862t6l
- 此快照首次捕获于
- 2025/11/21 09:13 4 个月前
- 此快照最后确认于
- 2025/11/21 09:48 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
int dis[10010];
struct cmp1{
bool operator () (int &a,int &b)
{
return dis[a]>dis[b];
}
};
priority_queue<int,vector<int>,cmp1> Q;
int vis[10010];
int f[10010];
int bf[10010][10010];
vector<int> G[10010];
int main()
{
// freopen("bee.in","r",stdin);
// freopen("bee.out","w",stdout);
int n,m,u,v,T;
scanf("%d%d%d%d%d",&n,&m,&u,&v,&T);
for(int i=1;i<=n;i++)
scanf("%d",&f[i]);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(bf[a][b]||bf[b][a])
{
bf[a][b]=min(bf[a][b],c);
bf[b][a]=bf[a][b];
continue;
}
G[a].push_back(b);
G[b].push_back(a);
bf[a][b]=bf[b][a]=c;
}
int low=1,high=1000000001;
int ans=-1;
while(low<=high)
{
int mid=(low+high)/2;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[u]=0;
Q.push(u);
do
{
int e=Q.top();
Q.pop();
if(vis[e]) continue;
vis[e]=1;
int sz=G[e].size();
for(int i=0;i<sz;i++)
{
int t=G[e][i];
if(f[t]>mid) continue;
if(dis[t]>dis[e]+bf[e][t])
{
dis[t]=dis[e]+bf[e][t];
Q.push(t);
}
}
}while(!Q.empty());
if(dis[v]>T)
low=mid+1;
else
{
ans=mid;
high=mid-1;
}
}
cout<<ans;
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...