蒟蒻第一次学次短路20ptsWA求条
查看原帖
蒟蒻第一次学次短路20ptsWA求条
982518
sjwhsss楼主2024/8/1 00:06

我这个哪里有问题

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+50;
int n , m , cnt =0 , head[maxn];
int dis[maxn][2];
struct edge
{
	int u , v, w , next;
}e[maxn];
void Insert(int u , int v, int w)
{
	e[++cnt].u=u , e[cnt].v=v , e[cnt].w=w , e[cnt].next=head[u] , head[u]=cnt;
}
struct point
{
	int u , d , vi = 0;
	point(int a , int b , int s) 
	{
		u=a , d=b , vi=s;
	}
	bool operator <(const point& x) const
	{
		return d > x.d;
	}
};
bool vis[maxn][2];
void dijkstra(int s)
{
	memset(vis , 0 , sizeof(vis));
	memset(dis , 0x3f , sizeof(dis));
	priority_queue <point>q;
	q.push(point(s , 0 , 0));
	dis[s][0]=0;
	while(!q.empty())
	{
		int u = q.top().u , d = q.top().d , vi = q.top().vi;
		q.pop();
		if (dis[u][1] < d)continue;
		for (int i = head[u]; i; i = e[i].next)
		{
			int v = e[i].v , w= e[i].w;
			if (dis[v][0] > d + w)
			{	
				dis[v][1]=dis[v][0];
				q.push(point(v , dis[v][1] , 1));
				dis[v][0]=d+w;
				q.push(point(v , dis[v][0] , 0));
			}
			else if (dis[v][1] > d + w && dis[v][0] != 0x3f3f3f3f)
			{
				dis[v][1]=d + w;
				q.push(point(v , dis[v][1] , 1));
			}
		}
	}
	return;
}
int main ()
{
	int r;
	cin >> n >> r;
	int u , v , w;
	for (int i = 1; i <= n; i++)
	{
		cin >> u >> v >> w;
		Insert(u , v , w);
		Insert(v , u , w);
	}
	dijkstra(1);
	cout << dis[n][1];
	return 0;
}
2024/8/1 00:06
加载中...