7 10 WA了……

囧……

2,3点超时。。。诡异。。其他0ms...太诡异了。。。。。。

fuck..我的指针~~

//p1082

type link=^p;

p=record

num:longint;

f,v:longint;

next:link;

end;

var map:array[0..10000]of link;

// link:array[1..5000,1..5000]of integer;

hp,mp:array[0..10000]of longint;

n,m,fx,fy,maxhp,nowhp,nowmp,minmp:longint;

procedure dfs(s:longint);

var i,j,q,p:longint; tp1:link;

begin

if nowhp>maxhp

then exit;

if (nowhp>hp) and (nowmp>mp)

then exit;

if (nowhp

前向星第一题～WA了好多好多好多次啊～

5000*5000的数组建议用integer.....longint崩掉内存了......

纯的DFS....加一个最优化剪枝即可(当前时间>最优时间退出)

好像不加也无所谓吧........数据弱的超乎想象........

type

link=^node;

node=record

num,f,v:longint;

next:link;

end;

var

g :array[0..5000] of link;

dist,time,stack :array[0..5000]of longint;

n,m,i,x,y,c,d,s,t,k,ans :longint;

visit :array[0..5000]of boolean;

e :link;

procedure dfs(p,tot,sum:longint);

var

i :longint;

e :link;

begin

visit[p]:=true;

if p=t then ans:=sum else

begin

e:=g[p];

while enil do

begin

if not visit[e^.num] then

if (tot+dist[e^.num]+e^.fdist[stack[head]]+e^.f then

begin

dist[e^.num]:=dist[stack[head]]+e^.f;

if not visit[e^.num] then

begin

visit[e^.num]:=true;

inc(tail);

if tail>n then tail:=1;

stack[tail]:=e^.num;

end;

end;

e:=e^.next;

end;

visit[stack[head]]:=false;

end;

end;

procedure spfa2;

var

head,tail,i :longint;

e :link;

begin

fillchar(time,sizeof(time),1shl 7-1);

fillchar(visit,sizeof(visit),false);

time[t]:=0;

stack[1]:=t;

head:=0;

tail:=1;

while headtail do

begin

inc(head);

if head>n then head:=1;

e:=g[stack[head]];

while enil do

begin

if time[e^.num]>time[stack[head]]+e^.v then

begin

time[e^.num]:=time[stack[head]]+e^.v;

if not visit[e^.num] then

begin

visit[e^.num]:=true;

inc(tail);

if tail>n then tail:=1;

stack[tail]:=e^.num;

end;

end;

e:=e^.next;

end;

visit[stack[head]]:=false;

end;

end;

begin

read(n,m);

for i:=1 to n do

begin

new(g[i]);

g[i]:=nil;

end;

for i:=1 to m do

begin

read(x,y,c,d);

if x=y then continue;

new(e);

e^.num:=y;

e^.f:=c;

e^.v:=d;

e^.next:=g[x];

g[x]:=e;

new(e);

e^.num:=x;

e^.f:=c;

e^.v:=d;

e^.next:=g[y];

g[y]:=e;

end;

read(s,t,k);

spfa1;

spfa2;

ans:=maxlongint;

fillchar(visit,sizeof(visit),false);

dfs(s,0,0);

if ans

数据太水了，很朴素的DFS也能轻松秒杀。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

代码也很短，不到40行：

program p1082;var a:array[1..5000,1..5000,1..3] of longint; c,b:array[1..5000] of longint; i,j,k,x,y,tl,qd,zd,n,m,mint:longint;procedure dfs(k,s,t:longint);var i:longint;begin if k=zd then begin mint:=t; exit; end; for i:=1 to c[k] do if (b[a[k,i,1]]=0)and(s+a[k,i,2]

Accepted 有效得分：100 有效耗时：0ms

我要笑喷了……………………

这题的标准解法应该是用队列维护状态然后SPFA预处理+SPFA+前向星

(P.S 前向星很简单，自己查去就知道了)

可是我只写了预处理就过了- -!

Orz，这题数据真的很水啊~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

管理员千万别删代码，我要贴关键部分出来警醒后人………………

（实在要删也没关系）

void solve()

{SPFA1(start,best_k);

if(best_k[finish]>kk) {printf("-1"); return ;}

memset(best_k,0,sizeof(best_k));

SPFA2(start,best_t);

printf("%d",best_t[finish]);

//final_SPFA(start); //本来准备写的，但是还没写就过了- -!

}

int main()

{init();

solve();

return 0;

}

欢迎大家来我的博客看看：

http://hi.baidu.com/wx405557858

神奇的SPFA……很全能啊。。

感谢各位大牛的赐教，又让我学会了一种新方法！

SPFA+前向星

---|---|---|---|---|---|---|---|---|---|--

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DFS+前向星

前向星要开双倍的大小，因为是无向图。

第一次用前向星这玩意，还蛮好用的。（qsort+记录起点）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

二次SPFA

水题一道~

注意SPFA更新条件除了时间之外AND 体力消耗

第二个点为什么不过？？

啊!!!

DFS 秒杀!!!

想都没想就写了个 E[40001];

突然发现是无向图,那个最大值应该乘2了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

还没测提交就90

典型SPFA变种

这题数据是不是太水了...........?

#include

#include

using namespace std;

const int MAX = 5000;

struct vertex{

int n;

int length;

int cost;

};

vector < vertex > graph[MAX];

int color[MAX];

int n;

int m;

long long heath;

int ans;

int s;

int v;

void DFS(int st,int h,int t){

if( t < ans && h n >> m;

int st,vd,ct,le;

for(int i=0;i> st >> vd >> ct >> le;

vertex one;

one.n = vd - 1;

one.length = le;

one.cost = ct;

graph[st-1].push_back(one);

vertex other;

other.n = st - 1;

other.cost = ct;

other.length = le;

graph[vd-1].push_back(other);

}

cin >> s >> v;

cin >> heath;

ans = 0xffffff;

s--;

v--;

DFS(s,0,0);

if(ans == 0xffffff){

cout

数据很弱，用DFS都能秒杀。

记得要用邻接表，还要加上最优化剪枝。

想不到2009年A的第一题竟是这题..

既然可以用简单的DFS+前向星解决也懒的写SPFA了

第一次忘了考虑无解的情况90

2009年,新的开始.