kuangbin_ShortPath R (HDU 4370)

出题人真是脑洞堪比黑洞 (然后自己也被吸进去了

理解一遍题意 三个条件可以转化为 1的出度是1, n的入度是1, 2~n-1的出度等于入度

不难发现1-n的最短路符合题意 然而其实还有另一种情况 1为起止点的最短闭环+n为起止点的最短闭环同样满足要求

因此取两者的min作为结果

#include <iostream>

#include <string>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <queue>

#include <map>

#include <vector>

#include <set>

#include <algorithm>

#define INF 0x3F3F3F3F

using namespace std;

int n, val[][];

int dist[];

bool vis[];

void spfa(int s)

{

    //计算最短闭环 因此入队节点不是1而是其他所有点

    memset(vis, false, sizeof vis);

    memset(dist, 0x3f, sizeof dist);

    queue<int> q;

    for(int i = ; i <= n; i++){

        if(i == s) continue;

        dist[i] = val[s][i];

        q.push(i);

        vis[i] = true;

    }

    while(!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = ; i <= n; i++){

            if(i == u) continue;

            if(dist[i] > dist[u] + val[u][i]){

                dist[i] = dist[u] + val[u][i];

                if(!vis[i]){

                    vis[i] = true;

                    q.push(i);

                }

            }

        }

    }

}

int main()

{

    int path, dist1, distn;

    int ans;

    while(~scanf("%d", &n)){

        for(int i = ; i <= n; i++){

            for(int j = ; j <= n; j++){

                scanf("%d", &val[i][j]);

            }

        }

        spfa();

        path = dist[n];

        dist1 = dist[];

        spfa(n);

        distn = dist[n];

        printf("%d\n", min(dist1 + distn, path));

    }

    return ;

}