TC SRM 583 DIV 2

做了俩，rating涨了80。第二个题是关于身份证的模拟题，写的时间比较长，但是我认真检查了。。。
第三个题是最短路，今天写了写，写的很繁琐，写的很多错。
  1 #include <cstring>
  2 #include <cstdio>
  3 #include <string>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <vector>
  7 #include <queue>
  8 using namespace std;
  9 #define INF 0xfffffff
 10 vector<string>::iterator it;
 11 int p[101][101];
 12 int a[4] = {0,0,1,-1};
 13 int b[4] = {1,-1,0,0};
 14 struct node
 15 {
 16     int u,v,w,next;
 17 }edge[1000001];
 18 int first[2001];
 19 int in[2001],d[2001];
 20 int tot;
 21 void CL()
 22 {
 23     memset(first,-1,sizeof(first));
 24     tot = 0;
 25 }
 26 void add(int u,int v,int w)
 27 {
 28     edge[tot].u = u;
 29     edge[tot].v = v;
 30     edge[tot].w = w;
 31     edge[tot].next = first[u];
 32     first[u] = tot ++;
 33 }
 34 int spfa(int x,int n,int key)
 35 {
 36     int i,u,v;
 37     queue<int> que;
 38     for(i = 1;i <= n;i ++)
 39     {
 40         in[i] = 0;
 41         d[i] = INF;
 42     }
 43     in[x] = 0;
 44     d[x] = key;
 45     que.push(x);
 46     while(!que.empty())
 47     {
 48         u = que.front();
 49         que.pop();
 50         in[u] = 0;
 51         for(i = first[u];i != -1;i = edge[i].next)
 52         {
 53             v = edge[i].v;
 54             if(d[v] > d[u] + edge[i].w)
 55             {
 56                 d[v] = d[u] + edge[i].w;
 57                 if(!in[v])
 58                 {
 59                     in[v] = 1;
 60                     que.push(v);
 61                 }
 62             }
 63         }
 64     }
 65     int ans = 0;
 66     for(i = 1;i <= n;i ++)
 67     {
 68         if(i != x)
 69         ans = max(ans,d[i]);
 70     }
 71     return ans;
 72 }
 73 class GameOnABoard
 74 {
 75 public:
 76     int optimalChoice(vector <string> cost)
 77     {
 78         int i,j,k,n,len,ans;
 79         n = 1;
 80         CL();
 81         for(it = cost.begin();it != cost.end();it ++)
 82         {
 83             len = 0;
 84             for(j = 1;j <= (*it).size();j ++)
 85             {
 86                 p[n][j] = (*it)[j-1] - '0';
 87                 len ++;
 88             }
 89             n ++;
 90         }
 91         n --;
 92         for(i = 1;i <= n;i ++)
 93         {
 94             for(j = 1;j <= len;j ++)
 95             {
 96                 for(k = 0;k < 4;k ++)
 97                 {
 98                     if(i+a[k] >= 1&&i + a[k] <= n&&j + b[k] >= 1&&j + b[k] <= len)
 99                     {
100                         add((i-1)*len+j,(i+a[k]-1)*len+j+b[k],p[i+a[k]][j+b[k]]);
101                     }
102                 }
103             }
104         }
105         ans = 1000000000;
106         for(i = 1;i <= n;i ++)
107         {
108             for(j = 1;j <= len;j ++)
109             ans = min(ans,spfa((i-1)*len+j,n*len,p[i][j]));
110         }
111         return ans;
112     }
113 };