DIJ(单源次短路) - Two Paths - HDU 6181

DIJ(次短路) - Two Paths - HDU 6181

题意：

$给定一个n个点，m条边的无向图，$

$计算次短路(与最短路至少有一条边不同)。$

输入：

$T组测试数据，$

$每组数据首行包括两个正整数n和m，$

$接着m行输入m条边，每行有三个正整数，u、v、w，表示点u和v之间有一条权值为w的无向边。$

输出:

$次短路长度。$

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

数据范围:

$1\le T\le 15，2\le n,m\le 100000，1\le u,v\le n,1\le w\le 1000000000$

---

分析：

$求次短路，用两个数组分别维护最短路和次短路即可。$

$需要注意的是：由于是无向图，次短路至多经过同一点2次，若某次扩展到的点已经经过了两次，就直接跳过。$

$另外，边的权值较大，注意爆int。$

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

#define ll long long
#define P pair<ll,int>
#define x first
#define y second

using namespace std;

const int N=1e5+10,M=2e5+10;

int n,m;
int st[N];
int e[M],ne[M],h[N],idx;
ll w[M];
ll dis[2][N];

void add(int a,int b,ll c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

ll dijkstra()
{
    memset(dis,0x3f,sizeof dis);   
    memset(st,0,sizeof st);
    dis[0][1]=0;
    
    priority_queue<P,vector<P>,greater<P>> heap;
    heap.push({0,1});
    
    while(heap.size())
    {
        P t=heap.top();
        heap.pop();
        
        int ver=t.y;
        ll d=t.x;
        st[ver]++;
        
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(st[j]==2) continue;

            if(dis[0][j]>d+w[i])
            {
                dis[1][j]=dis[0][j];
                dis[0][j]=d+w[i];
                heap.push({dis[0][j],j});
            }
            else if(dis[1][j]>d+w[i])
            {
                dis[1][j]=d+w[i];
                heap.push({dis[1][j],j});
            }
        }
    }
    return dis[1][n];
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(h,-1,sizeof h);
        idx=0;

        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
            int a,b;
            ll c;
            scanf("%d%d%lld",&a,&b,&c);
            add(a,b,c), add(b,a,c);
        }
        printf("%lld\n",dijkstra());
    }
    
    return 0;
}