F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 1001 >> 数据都下回来测了结果交上去无限WA
danihao123 @ 2016-01-28 12:15:14
[ Quote ] [ Edit ] [ Delete ] 1#
求解啊!
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cctype>
using namespace std;
typedef unsigned long ul;
const int maxn=2000000;
const ul INF=0xefefefef;
int n,m,t;
ul ansans=INF;
bool vavava=false;
// 图相关
struct Edge{
int u,v;
ul d;
Edge(int a,int b,ul c){
u=a;
v=b;
d=c;
}
};
vector<Edge> edges;
vector<int> G[maxn];
void Add_Edge(int x,int y,ul z){
G[x].push_back(edges.size());
edges.push_back(Edge(x,y,z));
}
// 读入优化
inline ul readint(){
char c=getchar();
register ul x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
// 读入并建图
void build_graph(){
int i,j,po,a,b;
ul u;
n=readint();
m=readint();
if(n==1 || m==1){
vavava=true;
while(scanf("%lu",&u)==1){
ansans=min(ansans,u);
}
return;
}
t=2*m*n-2*n-2*m+3;
po=2*(m-1);
for(i=1;i<m;i++){
u=readint();
a=2*i-1;
Add_Edge(a,t,u);
Add_Edge(t,a,u);
}
for(i=2;i<=(n-1);i++){
for(j=1;j<m;j++){
u=readint();
a=po*(i-1)+2*j-1;
b=2*j+po*(i-2);
Add_Edge(a,b,u);
Add_Edge(b,a,u);
}
}
for(i=1;i<m;i++){
u=readint();
a=2*i+po*(n-2);
Add_Edge(a,0,u);
Add_Edge(0,a,u);
}
for(i=1;i<n;i++){
u=readint();
a=2+po*(i-1);
Add_Edge(0,a,u);
Add_Edge(a,0,u);
for(j=1;j<(m-1);j++){
u=readint();
a=2*j-1+po*(i-1);
b=2*(j+1)+po*(i-1);
Add_Edge(a,b,u);
Add_Edge(a,b,u);
}
u=readint();
a=2*m-3+po*(i-1);
Add_Edge(a,t,u);
Add_Edge(t,a,u);
}
for(i=1;i<n;i++){
for(j=1;j<m;j++){
u=readint();
a=po*(i-1)+2*j;
b=a-1;
Add_Edge(a,b,u);
Add_Edge(b,a,u);
}
}
return;
}
bool vis[maxn];
// int cnt[maxn];
ul d[maxn];
queue<int> Q;
ul SPFA(){
register int i,k;
memset(d,0xef,sizeof(d));
memset(vis,0,sizeof(vis));
// memset(cnt,0,sizeof(cnt));
d[0]=0;
Q.push(0);
vis[0]=true;
while(!Q.empty()){
k=Q.front();
Q.pop();
vis[k]=false;
for(i=0;i<G[k].size();i++){
Edge& e=edges[G[k][i]];
if(d[k]<INF && d[e.v]>e.d+d[k]){
d[e.v]=d[k]+e.d;
if(!vis[e.v]){
Q.push(e.v);
vis[e.v]=true;
}
}
}
}
return d[t];
}
int main(){
build_graph();
if(vavava){
printf("%lu\n",ansans);
return 0;
}
printf("%lu\n",SPFA());
return 0;
}
danihao123 @ 2016-02-01 12:14:49
[ Quote ] [ Edit ] [ Delete ] 2#
顶顶顶
diaosipan1 @ 2016-05-04 19:51:31
[ Quote ] [ Edit ] [ Delete ] 3#
我也是,都不知道WA了多少遍了,而且都是0MS WA,向网站要的那些数据都过了啊
lavendir @ 2016-05-04 23:45:16
[ Quote ] [ Edit ] [ Delete ] 4#
有可能是少给了最后一组数据,再发邮件吧。
Vector_W @ 2016-05-16 20:15:03
[ Quote ] [ Edit ] [ Delete ] 5#
求教 数据从哪里下
1327246148 @ 2017-03-14 22:03:51
[ Quote ] [ Edit ] [ Delete ] 6#
RT,我也莫名WA,黄学长的代码我都找出来错了,可还没找出来我代码的错,,蓝瘦,香菇
infinityedge @ 2017-03-30 20:35:19
[ Quote ] [ Edit ] [ Delete ] 7#
千古神犇danihao123,数据结构碾压众生
owojiecao @ 2019-07-17 16:38:19
[ Quote ] [ Edit ] [ Delete ] 8#
欸请问数据在哪下啊quq
[Top] [Previous Page] [Next Page]

HOME Back