HDU4370(0 or 1)
2018-10-09 本文已影响1人
kimoyami
链接:https://vjudge.net/contest/254476#problem/R
思路:这道题很巧妙,我以为是模拟建图,没有看出来新矩阵可以看作一个1-n的邻接矩阵,且保证1的出度为1,n的入度为1,相当于求一个1-n的最短路,或者是一个1出发的自环+一个n出发的自环,只要看出来了这个题就很简单了,按思路建图跑两遍最短路即可。(注意1开始的距离并不是0,所以迪杰斯特拉不适用,这时候用spfa比较好)
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500*500;
const int INF = 1e9;
int a[500][500];
typedef pair<int,int> P;
struct edge{
int from,to,dist;
};
struct Dij{
int n,m;
vector<int> G[maxn];
vector<edge> edges;
int d[maxn];
int inq[maxn];
int cnt[maxn];
void init(int n){
this->n = n;
for(int i=0;i<=n;i++)G[i].clear();
edges.clear();
}
void addedge(int from,int to,int dist){
edges.push_back(edge{from,to,dist});
m = edges.size();
G[from].push_back(m-1);
}
bool spfa(int s){
queue<int> Q;
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
{
if(i==s)
{
d[s]=1e9;continue;
}
d[i]=a[s][i];
inq[i]=1;
Q.push(i);
}
Q.push(s);
while(!Q.empty()){
int u = Q.front();
Q.pop();
inq[u] = false;
for(int i=0;i<G[u].size();i++){
edge& e = edges[G[u][i]];
if(d[e.to]>d[u]+e.dist){
d[e.to] = d[u] + e.dist;
if(!inq[e.to]){
Q.push(e.to);
inq[e.to] = true;
if(++cnt[e.to]>n){
return true;
}
}
}
}
}
return false;
}
}solver;
int n;
int main(){
while(~scanf("%d",&n)){
solver.init(n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
solver.addedge(i,j,a[i][j]);
}
}
solver.spfa(1);
int ans1 = solver.d[n];
int loop1 = solver.d[1];
solver.spfa(n);
int loop2 = solver.d[n];
printf("%d\n",min(loop1 + loop2,ans1));
}
return 0;
}