hdu4370 dijkstra矩阵转单向边最短路矩阵+自环闭环-白红宇

hdu4370 dijkstra矩阵转单向边最短路矩阵+自环闭环

阅读量：5234 次

发布时间：2019-06-14

本文共 994 字，大约阅读时间需要 3 分钟。

矩阵太神奇了Orz，网上的题解大多是spfa，不过我发想dijkstra也能做

把n*n的矩阵看成是单向边距离矩阵就行

#include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 500#define INF 1<<30using namespace std;int a[MAXN][MAXN];int n;int dist[MAXN],vis[MAXN];int dijkstra(int s,int t){    memset(dist,0,sizeof dist);     memset(vis,0,sizeof vis);    for(int i=0;i<=n;i++)        if(i==s)            dist[i]=INF;        else             dist[i]=a[s][i];        while(1){        int k=-1;        int Min=INF;        for(int i=1;i<=n;i++)            if(!vis[i]&&dist[i]
         
          dist[k]+a[k][i])                dist[i]=dist[k]+a[k][i];    }    return dist[t];}int main(){    while(scanf("%d",&n)==1){        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)                scanf("%d",&a[i][j]);                printf("%d\n",min(dijkstra(1,n),dijkstra(1,1)+dijkstra(n,n)));    }    return 0;}