HDU 6181Two Paths——————（求次短路）

妖狐艹你老母 2022-04-12 13:23 116阅读 0赞

# Two Paths #

**Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 153428/153428 K (Java/Others)  
Total Submission(s): 2139 Accepted Submission(s): 834**

Problem Description

You are given a undirected graph with n nodes (numbered from 1 to n) and m edges. Alice and Bob are now trying to play a game.  
Both of them will take different route from 1 to n (not necessary simple).  
Alice always moves first and she is so clever that take one of the shortest path from 1 to n.  
Now is the Bob's turn. Help Bob to take possible shortest route from 1 to n.  
There's neither multiple edges nor self-loops.  
Two paths S and T are considered different if and only if there is an integer i, so that the i-th edge of S is not the same as the i-th edge of T or one of them doesn't exist.

Input

The first line of input contains an integer T(1 <= T <= 15), the number of test cases.  
The first line of each test case contains 2 integers n, m (2 <= n, m <= 100000), number of nodes and number of edges. Each of the next m lines contains 3 integers a, b, w (1 <= a, b <= n, 1 <= w <= 1000000000), this means that there's an edge between node a and node b and its length is w.  
It is guaranteed that there is at least one path from 1 to n.  
Sum of n over all test cases is less than 250000 and sum of m over all test cases is less than 350000.

Output

For each test case print length of valid shortest path in one line.

Sample Input

2
    3 3
    1 2 1
    2 3 4
    1 3 3
    2 1
    1 2 1

Sample Output

5
    3
    
       
        
        
         
         
          Hint
        
         
    For testcase 1, Alice take path 1 - 3 and its length is 3, and then Bob will take path 1 - 2 - 3 and its length is 5.
    For testcase 2, Bob will take route 1 - 2 - 1 - 2  and its length is 3

--------------------

给定多张无向图，求出每张图中的从s到t的次短路

Input  
第一行一个数T，表示数据组数  
后面给出T张无向图

Output  
对每一张图，给出其次短路

--------------------

裸的次短路问题  
G\[i\]忘清空了，WA了好多次，  
难受。  
很难受。

#include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    typedef long long ll;
    typedef pair<ll,ll> P;
    const ll INF  = 1e18;
    const int MAXN = 2e5+7;
    struct edge{
        
            ll to,cost;
            edge(){
        };
            edge(ll _to, ll _cost)
            {
        
                    to = _to;
                    cost = _cost;
            }
    };
    
    vector<edge> G[MAXN];
    int n,m;
    ll dist[MAXN];
    ll dist2[MAXN];
    
    void slove()
    {
        
            priority_queue<P, vector<P>, greater<P> >que;
            fill(dist, dist + n + 1, INF);
            fill(dist2,dist2+ n + 1, INF);
            dist[0] = 0;
            que.push(P(0,0));
            while(!que.empty())
            {
        
                    P p = que.top(); que.pop();
                    ll v = p.second, d = p.first;
                    if(dist2[v] < d)        continue;
                    for(int i = 0; i < G[v].size(); ++i )
                    {
        
                            edge &e = G[v][i];
                            ll d2 = d + e.cost;
                            if(dist[e.to] > d2)
                            {
        
                                    swap(dist[e.to], d2);
                                    que.push(P(dist[e.to], e.to));
                            }
                            if(dist2[e.to] > d2 && dist[e.to] < d2)
                            {
        
                                    dist2[e.to] = d2;
                                    que.push(P(dist2[e.to],e.to));
                            }
                    }
            }
            printf("%lld\n",dist2[n-1]);
    }
    int main()
    {
        
            int t;
            scanf("%d",&t);
            while(t--)
            {
        
                    scanf("%d %d",&n,&m);
                    ll x,y,z;
                    for(int i=0;i<=n;i++)
                            G[i].clear();
                    for(int i=0;i<m;i++)
                    {
        
                            scanf("%lld %lld %lld",&x,&y,&z);
                            G[x-1].push_back(edge(y-1, z));
                            G[y-1].push_back(edge(x-1, z));
                    }
                    slove();
            }
            return 0;
    }