做了俩,rating涨了80。第二个题是关于身份证的模拟题,写的时间比较长,但是我认真检查了。。。

第三个题是最短路,今天写了写,写的很繁琐,写的很多错。

 #include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
vector<string>::iterator it;
int p[][];
int a[] = {,,,-};
int b[] = {,-,,};
struct node
{
int u,v,w,next;
}edge[];
int first[];
int in[],d[];
int tot;
void CL()
{
memset(first,-,sizeof(first));
tot = ;
}
void add(int u,int v,int w)
{
edge[tot].u = u;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = first[u];
first[u] = tot ++;
}
int spfa(int x,int n,int key)
{
int i,u,v;
queue<int> que;
for(i = ;i <= n;i ++)
{
in[i] = ;
d[i] = INF;
}
in[x] = ;
d[x] = key;
que.push(x);
while(!que.empty())
{
u = que.front();
que.pop();
in[u] = ;
for(i = first[u];i != -;i = edge[i].next)
{
v = edge[i].v;
if(d[v] > d[u] + edge[i].w)
{
d[v] = d[u] + edge[i].w;
if(!in[v])
{
in[v] = ;
que.push(v);
}
}
}
}
int ans = ;
for(i = ;i <= n;i ++)
{
if(i != x)
ans = max(ans,d[i]);
}
return ans;
}
class GameOnABoard
{
public:
int optimalChoice(vector <string> cost)
{
int i,j,k,n,len,ans;
n = ;
CL();
for(it = cost.begin();it != cost.end();it ++)
{
len = ;
for(j = ;j <= (*it).size();j ++)
{
p[n][j] = (*it)[j-] - '';
len ++;
}
n ++;
}
n --;
for(i = ;i <= n;i ++)
{
for(j = ;j <= len;j ++)
{
for(k = ;k < ;k ++)
{
if(i+a[k] >= &&i + a[k] <= n&&j + b[k] >= &&j + b[k] <= len)
{
add((i-)*len+j,(i+a[k]-)*len+j+b[k],p[i+a[k]][j+b[k]]);
}
}
}
}
ans = ;
for(i = ;i <= n;i ++)
{
for(j = ;j <= len;j ++)
ans = min(ans,spfa((i-)*len+j,n*len,p[i][j]));
}
return ans;
}
};
05-10 23:17