【HDOJ】4370 0 or 1

面白いテーマですね.式の条件に注意する.等式1は実際に点1を表す出度が1であり、等式2は実際に点2を表す入度が1であり、等式は他の点を中間点とし、入度と出度が等しいことを表す.最短ルートに簡単に変換できます.spfaは直接求められ,Cは隣接行列である.同時に,1点出発,最終的に1点に戻るループ,n点出発,最終的にn点に戻るループが存在する可能性がある.

  1 /* 4370 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int INF = 0x3f3f3f3f;
 44 const int maxn = 305;
 45 int C[maxn][maxn];
 46 int dis[maxn];
 47 bool visit[maxn];
 48 int n;
 49 
 50 void spfa(int s) {
 51     queue<int> Q;
 52     int u;
 53     
 54     rep(i, 1, n+1) {
 55         if (s == i) {
 56             dis[i] = INF;
 57         } else {
 58             dis[i] = C[s][i];
 59             visit[i] = true;
 60             Q.push(i);
 61         }
 62     }
 63     
 64     while (!Q.empty()) {
 65         u = Q.front();
 66         Q.pop();
 67         visit[u] = false;
 68         rep(v, 1, n+1) {
 69             if (dis[v] > dis[u]+C[u][v]) {
 70                 dis[v] = dis[u] + C[u][v];
 71                 if (!visit[v]) {
 72                     visit[v] = true;
 73                     Q.push(v);
 74                 }
 75             }
 76         }
 77     }
 78 }
 79 
 80 void solve() {
 81     int ans, tmp;
 82     
 83     spfa(1);
 84     ans = dis[n];
 85     tmp = dis[1];
 86     spfa(n);
 87     tmp += dis[n];
 88     
 89     ans = min(ans, tmp);
 90     printf("%d
", ans);
 91 }
 92 
 93 int main() {
 94     ios::sync_with_stdio(false);
 95     #ifndef ONLINE_JUDGE
 96         freopen("data.in", "r", stdin);
 97         freopen("data.out", "w", stdout);
 98     #endif
 99     
100     while (scanf("%d", &n)!=EOF) {
101         rep(i, 1, n+1)
102             rep(j, 1, n+1)
103                 scanf("%d", &C[i][j]);
104         solve();
105     }
106     
107     #ifndef ONLINE_JUDGE
108         printf("time = %d.
", (int)clock());
109     #endif
110     
111     return 0;
112 }