社区讨论

好难受啊,求助大佬,改了一年

学术版参与者 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 条回复,欢迎继续交流。

正在加载回复...