F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 1001 >> spfa 3900MS
xiang556 @ 2018-07-11 07:36:24
[ Quote ] [ Edit ] [ Delete ] 1#
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <limits.h>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l+r)>>1)
#define fst first
#define snd second
#define sfn scanf("%d",&n)
#define sfnm scanf("%d%d",&n,&m)
#define sft scanf("%d",&t)
#define pfans printf("%d\n",ans)
using namespace std;
typedef long long lint;

const int MAXN = 1e6 + 10;

struct star{
int to,w;
};

vector<star> g[2 * MAXN];
int st,ed,dis[2 * MAXN],line[2 * MAXN],n,m;
bool have[2 * MAXN];

int cul(int i,int j){
return (i - 1) * (m - 1) + j;
}

void add(int u,int v,int w){
star x; x.to = v; x.w = w;
g[u].push_back(x);
x.to = u;
g[v].push_back(x);
}

void next(int &x){
++x;
if(x > 1000002){
x = 0;
}
}

void spfa(){
int qst,qed,num;
qst = qed = 0; num = 1;
memset(dis,0x7f,sizeof(dis));
memset(have,false,sizeof(have));
have[st] = true;
dis[st] = 0;
line[0] = st;
while(num > 0){
int now = line[qst]; next(qst); --num;
for(int i = 0; i < g[now].size(); ++i){
if(dis[now] + g[now][i].w < dis[g[now][i].to]){
dis[g[now][i].to] = dis[now] + g[now][i].w;
if(!have[g[now][i].to]){
have[g[now][i].to] = true;
next(qed); line[qed] = g[now][i].to; ++num;
}
}
}
have[now] = false;
}
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(n == 1 && m == 1){
int num; scanf("%d",&num); printf("%d\n",num); continue;
}
st = 2 * (n - 1) * (m - 1) + 1; ed = st + 1;
for(int i = 1; i <= 2 * n * m; ++i){ g[i].clear();}
for(int i = 1; i <= n; ++i){
for(int j = 1; j < m; ++j){
int num; scanf("%d",&num);
if(i == 1){
add(st,cul(1,j),num);
}else if(i == n){
add(ed,cul(2 * (n - 1),j),num);
}else{
add(cul(2 * i - 1,j),cul(2 * i - 2,j),num);
}
}
}
for(int i = 1; i < n; ++i){
for(int j = 1; j <= m; ++j){
int num; scanf("%d",&num);
if(j == 1){
add(ed,cul(2 * i,j),num);
}else if(j == m){
add(st,cul(2 * i - 1,j - 1),num);
}else{
add(cul(2 * i,j),cul(2 * i - 1,j - 1),num);
}
}
}

for(int i = 1; i < n; ++i){
for(int j = 1; j < m; ++j){
int num; scanf("%d",&num);
add(cul(2 * i,j),cul(2 * i - 1,j),num);
}
}

spfa();
printf("%d\n",dis[ed]);
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back