hdu 4370 最短路 邻接矩阵表示 模型的抽象

参考博客：https://blog.csdn.net/llx523113241/article/details/47668107

题目大意：有一个矩阵C[i][j]，和一个由01组成的矩阵X[i][j]。X矩阵满足条件：

1.X 12+X 13+…X 1n=1

2.X 1n+X 2n+…X n-1n=1

3.for each i (1 < i < n) , satisfies ∑X ki (1<=k<=n)=∑X ij (1<=j<=n).

现在要求最小的∑C ij*X ij。

解题思路：思维转换过来就好做了。从第一个条件可以看出一号结点出度为1，从第二个条件可以看出n号节点的入度为1，从第三个条件可以看出2~n-1号节点的入度必须等于出度。所以可以直接把C[i][j]看成是一张邻接矩阵，1为起点，n为终点，跑一次最短路，求出最短路sp。

这是其中一种情况，还有另一种情况满足题目条件，就是，1号结点有非自环的闭环，n号结点也有非自环的闭环。以1为起点，但d[1]置为INF，且起点不入队列，而让，与1号结点连向的点进入队列，然后跑最短路，最后d[1]就是1结点的最小闭环b1，n的最小闭环b2同理。

所以最后答案就是min(sp, b1 + b2)。

这题难的就是把这个模型抽象出来了。。。将图的邻接矩阵表示法 和这个矩阵关联

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;

#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair

const int N  =304;
const int INF = 1e9+3;

int n;
int c[303][303];
int x[403][333];
int d[N];
int vis[N];
//https://blog.csdn.net/llx523113241/article/details/47668107
void dij(int s){
    for(int i=1;i<=n;++i)d[i]=INF;
    memset(vis,0,sizeof(vis));

    d[s]=INF;

    for(int i=1;i<=n;++i){
        if(i==s)continue;
        d[i]= c[s][i];
    }

    while(1){
        int v=-1;
        for(int i=1;i<=n;++i){
            if(!vis[i] && (v==-1 ||d[i]<d[v]))v=i;
        }
        if(v==-1)break;vis[v]=1;
        for(int i=1;i<=n;++i){
            d[i]=min(d[i],d[v]+c[v][i]);
        }
    }
}

int main(){

    while(cin>>n){

        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j)
                scanf("%d",&c[i][j]);
        }
        dij(1);
        int dx = d[n];
        int d1 = d[1];
        dij(n);
        int d2= d[n];
        printf("%d
",min(dx,d1+d2));
    }
    return 0;
}