题意:题目巨晦涩的传递出1点和n点的初度等于入度等于1, 其余点出度和入度相等
分析:求最小和可以转换成求最短路,这样符合条件,但是还有一种情况.1点形成一个环,n点也形成一个环,这样也是可以的,这样SPFA要稍微修改点,d[s] = INF,表示可以更新.
#include <bits/stdc++.h>
using namespace std; const int N = 3e2 + 5;
const int INF = 0x3f3f3f3f;
int w[N][N];
int d[N];
bool vis[N];
int n; void SPFA(int s) {
memset (vis, false, sizeof (vis));
queue<int> que;
for (int i=1; i<=n; ++i) {
if (i == s) d[s] = INF;
else {
d[i] = w[s][i];
vis[i] = true;
que.push (i);
}
}
while (!que.empty ()) {
int u = que.front (); que.pop ();
vis[u] = false;
for (int i=1; i<=n; ++i) {
if (d[i] > d[u] + w[u][i]) {
d[i] = d[u] + w[u][i];
if (!vis[i]) {
vis[i] = true; que.push (i);
}
}
}
}
} int main(void) {
while (scanf ("%d", &n) == 1) {
for (int i=1; i<=n; ++i) {
for (int j=1; j<=n; ++j) {
scanf ("%d", &w[i][j]);
}
}
SPFA (1);
int ans = d[n];
int a1 = d[1];
SPFA (n);
int a2 = d[n];
printf ("%d\n", min (ans, a1 + a2));
} return 0;
}