Submission #2464003

---

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