HDU - 4370 题目链接
我看到这道题的时候就是一脸懵，这能用最短路求解？？？
解题方法
条件
1.X12+X13+...X1n=1
2.X1n+X2n+...Xn-1n=1
3.for each i (1<i<n), satisfies ∑Xki (1<=k<=n)=∑Xij (1<=j<=n).
题意理解
- 对于第一条我们可以理解为，点1只能出去一次，也就是点1的出度为1。
- 对于第二条我们可以理解为，点n只能进来一次，也就是点n的入度为1。
- 对于第三条我们可以理解为，点（1，n）的出度和入度相等并且都是1。
而这道题目的意思就是求解经过点1，和点n的最短路，显然我们有两种情况。
一、一条直线从1 -> n。
二、以点1形成一个环，以点n形成一个环。
答案就是上述两种情况的最小值。
代码
//Powered by CK 2020:04:08
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 310;
int maze[N][N], visit[N], dis[N], n;
void spfa(int rt) {
queue<int> q;
for(int i = 1; i <= n; i++) {
if(i != rt) {//因为可能是求环问题，我们把起始点设置为无穷大。
visit[i] = 1;
dis[i] = maze[rt][i];
q.push(i);
}
else {
dis[i] = INF;
visit[i] = 0;
}
}
while(!q.empty()) {//spfa的基本步骤。
int temp = q.front();
q.pop();
visit[temp] = 0;
for(int i = 1; i <= n; i++) {
if(dis[i] > dis[temp] + maze[temp][i]) {
dis[i] = dis[temp] + maze[temp][i];
if(!visit[i]) {
visit[i] = 1;
q.push(i);
}
}
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &maze[i][j]);
spfa(1);
int len = dis[n];//从1 -> n 的最短路
int cicle = dis[1];//以点1形成的环
spfa(n);
cicle += dis[n];//加上以点n形成的环
printf("%d
", min(len, cicle));//取最小值
}
return 0;
}