Submission #2463808

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstdio>
#include<cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <memory.h>
#include <vector>
#include<queue>
using namespace std;
struct Node
{
	int v, w;//v连向的下一个点，w长度
	Node(int a=0, int b=0)
	{
		v = a;
		w = b;
	}
};
bool operator < (const Node &a, const Node &b)
{
	return a.w > b.w;
}
const int maxn = 100000;
const int inf=10000000;
vector<Node> G[maxn*2];
int dis[maxn];
bool visit[maxn];
int N;
void init()
{
	for (int i = 0; i < N; i++)//n点数量
	{
		G[i].clear();
		dis[i] = inf;
		visit[i] = 0;
	}
}


int father[maxn];
void dijkstra(int from)//from 起点
{
	priority_queue<Node> que;
	dis[from] = 0;
	que.push(Node(from, 0));
	while (!que.empty())
	{
		Node n = que.top();
		que.pop();
		int u = n.v;//u是当前的点，v是下一个点
		if (visit[u])
		{
			continue;
		}
		visit[u] = 1;
		int glen = G[u].size();
		for (int i = 0; i < glen; i++)
		{
			int v = G[u][i].v;
			int w = G[u][i].w;
			if (!visit[v] && dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				father[v] = u;
				que.push(Node(v, dis[v]));
			}
		}
	}
}

int diss[maxn];
void dijkstraaaa(int from,int b,int e)//from 起点
{

	for (int i = 0; i < N; i++)//n点数量
	{
		diss[i] = inf;
		visit[i] = 0;
	}
	priority_queue<Node> que;
	diss[from] = 0;
	que.push(Node(from, 0));
	while (!que.empty())
	{
		Node n = que.top();
		que.pop();
		int u = n.v;//u是当前的点，v是下一个点
		if (visit[u])
		{
			continue;
		}
		visit[u] = 1;
		int glen = G[u].size();
		for (int i = 0; i < glen; i++)
		{
			if (u == b && G[u][i].v == e || u == e && G[u][i].v == b)continue;
			int v = G[u][i].v;
			int w = G[u][i].w;
			if (!visit[v] && diss[v] > diss[u] + w)
			{
				diss[v] = diss[u] + w;
				que.push(Node(v, diss[v]));
			}
		}
	}


}


int main()
{
	std::ios::sync_with_stdio(false);
	
	int m,be,en,x,y,z;
	cin >> N >> m >> be >> en;
	init();
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y >> z;
		x--, y--;
		G[x].push_back(Node(y,z));
		G[y].push_back(Node(x, z));
	}
	dijkstra(be-1);
	
	int ma = dis[en - 1];
	for (int i =en-1;i !=be-1;)
	{
		dijkstraaaa(father[i], father[i], i);//father[i]是i的上一个点，fatheri-i是关掉的道路，
		ma = max(diss[en - 1] + dis[father[i]] , ma);
		i = father[i];
	}
	if (ma = 10000000)ma = -1;
	cout << ma<<endl;
}

Submission Info

Judge Result