HDU 3986 最短路+枚举

这题HDU 1595 find the longest of the shortest 就是一模一样的

但是出现了重边，就比较恶心人了

然后就将输入的数据先排序，然后出现重边的肯定在一块，然后对每条边存储的是它最短的情况和次短的情况即可

/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define MAXN 1005
#define PI acos(-1.0)
using namespace std;
struct node
{
    int v, next;
    int w, worst;
    void init(){worst = INF; }
}edge[MAXN * MAXN];
int vis[MAXN], pre[MAXN], head[MAXN], d[MAXN];
int q[MAXN * MAXN];
int n, m, e;
struct wwj
{
    int u, v, w;
}in[MAXN * 100];
int uu[MAXN * 100], vv[MAXN * 100];
bool cmp(wwj x, wwj y)
{
    if(x.u == y.u && x.v == y.v) return x.w < y.w;
    else if(x.u == y.u) return x.v < y.v;
    else return x.u < y.u;
}
void insert(int x, int y, int w)
{
    int flag = 0;
    for(int i = head[x]; i != -1; i = edge[i].next)
    {
        if(edge[i].v == y)
        {
            if(edge[i].worst == INF && edge[i].w != INF) edge[i].worst = w;
            flag = 1;
            break;
        }
    }
    if(!flag)
    {
        edge[e].v = y;
        edge[e].w = w;
        edge[e].next = head[x];
        head[x] = e++;
    }
}
void spfa(int src)
{
    for(int i = 1; i <= n; i++)
        d[i] = INF;
    int h = 0, t = 1;
    memset(vis, 0, sizeof(vis));
    d[src] = 0;
    q[0] = src;
    vis[src] = 1;
    while(h < t)
    {
        int u = q[h++];
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if(d[v] > d[u] + w)
            {
                pre[v] = u;
                d[v] = d[u] + w;
                if(!vis[v])
                {
                    q[t++] = v;
                    vis[v] = 1;
                }
            }
        }
    }
}

void init()
{
    e = 0;
    memset(head, -1, sizeof(head));
    for(int i = 0; i < 5 * m; i++) edge[i].init();
}
void bechange(int u, int v)
{
    for(int i = head[u]; i != -1; i = edge[i].next)
        if(edge[i].v == v)
            swap(edge[i].w, edge[i].worst);
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        init();
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &in[i].u, &in[i].v, &in[i].w);
            in[i + m].u = in[i].v;
            in[i + m].v = in[i].u;
            in[i + m].w = in[i].w;
        }
        sort(in, in + 2 * m, cmp);
        for(int i = 0; i < 2 * m; i++)
            insert(in[i].u, in[i].v, in[i].w);
        spfa(1);
        int ans = d[n];
        int cnt = 0;
        for(int i = n; i != 1; i = pre[i])
        {
            uu[cnt] = i;
            vv[cnt] = pre[i];
            cnt++;
        }
        for(int i = 0; i < cnt; i++)
        {
            bechange(uu[i], vv[i]);
            bechange(vv[i], uu[i]);
            spfa(1);
            ans = max(ans, d[n]);
            bechange(uu[i], vv[i]);
            bechange(vv[i], uu[i]);
        }
        if(ans >= INF) puts("-1");
        else
        printf("%d\n", ans);
    }
    return 0;
}