HDU-4370 '0 or 1' 最短路 要考虑连通性

题目链接：https://cn.vjudge.net/problem/HDU-4370

题意

给一个矩阵C(nn)，要我们找到一个矩阵X(nn)，满足以下条件：

思路

如果把X当成一个邻接矩阵，可以发现本题就是要找一个图，满足以下条件：

1. 节点1有一个出度（注意不要1->1，因为要最小化边权），节点n有一个入度（同理不要n->n）
2. 其他节点出度等于入度
3. 最小化边权

很容易发现最短路是一种可能的情况（每个节点仅有一个出度入度）

另外还有一种情况需要考虑，就是起点和终点可以不连通，意思就是节点1节点n各参与一个互不连通的环

这还是要考虑连通问题啊

又没考虑，可烦，考虑开一个最短路专题总结一下

提交过程

WA1	没考虑连通性
WA2	int换long long
WA3	脑抽加上了1->1和n->n情况
AC	加上判断

代码

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=320;

const long long INF=1LL<<60;

typedef pair<long long, int> Node;

struct Cmp{

    bool operator () (const Node &a, const Node &b){

        return a.first>b.first;

    }

};

int G[maxn+5][maxn+5];

long long Dij(int n){

    long long dist[maxn+5], ans=0, circle1=INF, circle2=INF;

    priority_queue<Node, vector<Node>, Cmp> que;

    for (int i=0;i<=n; i++) dist[i]=INF;

    dist[1]=0;

    que.push(Node(dist[1], 1));

    while (que.size()){

        Node x=que.top(); que.pop();

        if (x.first!=dist[x.second]) continue;

        int &from=x.second;

        for (int to=1; to<=n; to++) if (to!=from){

            int &dis=G[from][to];

            if (to==1) circle1=min(circle1, dist[from]+dis);

            if (dist[to]<=dist[from]+(long long)dis) continue;

            dist[to]=dist[from]+(long long)dis;

            que.push(Node(dist[to], to));

        }

    }//return dist[n];

    ans=dist[n];

    for (int i=0;i<=n; i++) dist[i]=INF;

    dist[n]=0;

    que.push(Node(dist[n], n));

    while (que.size()){

        Node x=que.top(); que.pop();

        if (x.first!=dist[x.second]) continue;

        int &from=x.second;

        for (int to=1; to<=n; to++) if (to!=from){

            int &dis=G[from][to];

            if (to==n) circle2=min(circle2, dist[from]+dis);

            if (dist[to]<=dist[from]+(long long)dis) continue;

            dist[to]=dist[from]+(long long)dis;

            que.push(Node(dist[to], to));

        }

    }return min(ans, circle1+circle2);

}

int main(void){

    int n;

    while (scanf("%d", &n)==1 && n){

        for (int y=1; y<=n; y++)

            for (int x=1; x<=n; x++) scanf("%d", &G[y][x]);

        printf("%lld\n", Dij(n));

    }

    return 0;

}

1107ms

2012kB

1790

G++

2018-06-02 11:28:23