社区讨论

SPFA 本机样例能过,那为什么是0分???

P1396营救参与者 5已保存回复 9

讨论操作

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

当前回复
9 条
当前快照
1 份
快照标识符
@lo2f6rxt
此快照首次捕获于
2023/10/23 12:51
2 年前
此快照最后确认于
2023/10/23 12:51
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
struct edge{
	int to,w;
};
int t,s,m,n;
vector<edge> ve[10100];
int dis[10100];
bool book[10100];
signed main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
    	int u,v,w;
    	scanf("%d%d%d",&u,&v,&w);
    	ve[u].push_back(edge{v,w});
    	ve[v].push_back(edge{u,w});
	}
	for(int i=1;i<=n;i++)
	{
		if(i!=s)
		{
			dis[i]=1e9;
		}
	}
	queue<int> q;
	q.push(1);
	book[1]=1;
	while(!q.empty())
	{
		int v=q.front();
		q.pop();
		book[v]=0;
		for(int i=0;i<ve[v].size();i++)
		{
			int u=ve[v][i].to;
			if(max(dis[v],ve[v][i].w)<dis[u])
			{
				dis[u]=max(dis[v],ve[v][i].w);
				if(!book[u])
				{
					q.push(u);
					book[u]=1;
				}
			}
		}
	}
	cout<<dis[t];
    return 0;
}
测试输入:
3 3 1 3
1 2 2
2 3 1
1 3 3
测试输出:
2
评测全WA

回复

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

正在加载回复...