# HDU4370 0 or 1（建图转化+最短路径）

## 0 or 1

• Time Limit: 4000/2000 MS (Java/Others)
• Memory Limit: 32768/32768 K (Java/Others)
• Total Submission(s): 3269
• Accepted Submission(s): 1094

4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2

3

Snow_storm

### Source

2012 Multi-University Training Contest 8

### 链接

http://acm.hdu.edu.cn/showproblem.php?pid=4370

### 题意

• $X_{12} + X_{13} + ... + X_{1n} = 1$
• $X_{1n} + X_{2n} + ... + X_{(n-1)n} = 1$
• $\sum X_{ki} = \sum X_{ij}$ ($1 < k < n, 1 <= j <= n$)

### 题解

• 表示点1的出度为1
• 表示点n的入度为1
• 除了点1和点n外的其他点出入度相等

### 代码

StatusAccepted
Time655ms
Memory1752kB
Length1237
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 310;
int G[maxn][maxn];
int dist[maxn];
bool vis[maxn];
int n;

void spfa(int s)
{
queue <int> Q;
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; ++i)
{
if (i == s) // s点初始化为inf
dist[i] = inf;
else // 与s点连边的点入队
{
dist[i] = G[s][i];
Q.push(i);
vis[i] = true;
}
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = 1; i <= n; ++i)
{
if (dist[i] > dist[u] + G[u][i])
{
dist[i] = dist[u] + G[u][i];
if (!vis[i])
{
vis[i] = true;
Q.push(i);
}
}
}
vis[u] = false;
}
}

int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
scanf("%d", &G[i][j]);
spfa(1);
int ans = dist[n], cir1 = dist[1]; // 简单最短路径，“环1”
spfa(n);
int cirn = dist[n]; // "环n"
ans = min(ans, cir1 + cirn); // "环1+环n" 与简单最短路径最小值
printf("%d\n", ans);
}
return 0;
}

The end.
2018-09-06 星期四