#include

using namespace std;

struct Tedge{ int n,s; Tedge *next; };

Tedge *e[300];

int n,m,x,y,d[20000],dis[300],k;

bool f[300];

int main()

{

cin >> n ;

for (int i=1; inext=NULL;

}

for (;;)

{

cin >> x >> y >> k;

if ((x==0)&&(y==0)&&(k==0)) break;

Tedge *temp=new Tedge();

temp->n=y;

temp->s=k;

temp->next=e[x]->next;

e[x]->next=temp;

}

for (int i=1;is) > dis[temp->n] )

{

dis[temp->n] =min(dis[d[x]],temp->s);

if (!f[temp->n]) { f[temp->n]=true; y++; d[y]=temp->n;}

}

if (temp->next==NULL) break;

temp=temp->next;

}

f[d[x]]=false;

}

for (int i=2;i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

dij 直接秒杀 但 范围没看清 交了两次 囧

猥琐的过了。。。

时隔1年、、

终于沙茶的过了、、

就因为少打了个B:=FALSE;

教训、、

希望能仔细点、、

算法好像最小生成树的算法。。。

好像忘了那个最小生成树的贪心算法的名称。。。

汗。。。。

（好像叫PRIM）

看起来和DIJKSTRA差不多。。。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

之前写个插排0分。。。

没有任何优化的dij，还0ms..看看楼下众牛们..恩，计算机真是越来越来快了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

a:array[0..2000,0..2000] of longint;

d:array[1..2000] of longint;

v:array[1..2000] of boolean;

max,n,k,x,y,i,j:longint;

function min(c,d:longint):longint;

begin

if c>d then

exit(d)

else exit(c);

end;

begin

read(n);

read(x,y,a[x,y]);

while x0 do

read(x,y,a[x,y]);

for i:=2 to n do

d[i]:=a[1,i];

for i:=2 to n do

begin

max:=0;

for j:=1 to n do

if (d[j]>max)and(not v[j]) then

begin

max:=d[j];

k:=j;

end;

v[k]:=true;

for j:=1 to n do

if (not v[j])and(min(a[k,j],d[k])>d[j]) then

d[j]:=min(a[k,j],d[k]);

end;

for i:=2 to n do

writeln(d[i]);

end.

Orz神牛

for j:=1 to n do

if (not v[j])and(min(a[k,j],d[k])>d[j]) then

d[j]:=min(a[k,j],d[k]);

这句是啥意思？？？

连李寰都知道Dijkstra算法……

世界乱套了……

不过我还是没看懂题！MS是求单源最短路径的Bellman-Ford算法。

Dijkstra

编译通过...

├ 测试数据 01：[cloor=red]答案正确... 0ms

├

puppy测的DIJSKTRA 9ms 相当快

注意条件 一个都不能少 少一个就会过0个点（会被出题人夸可爱。。。）

xx:=min(dis[w],map[w,j]);

　　　　if not(v[j])and(map[w,j]>0)and(xx>dis[j])

　　　　then dis[j]:=xx;

太水了！

样例过了就交上去，结果AC了。

把dijkstra稍微改一下就行

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

好久没有一次AC了。

一个点到底几组数据？只有一组吗？题目的输入输出描述有明显的误导倾向！

在PUPPY上MS的程序,在VAG 6K上就成了

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

差距呀!

一开始G负错初值了 晕

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

按照前面某位大牛的思路编的代码

const

t=2000;

var

map:array[0..t,0..t] of longint;

v:array[0..t] of boolean;

dis:array[0..t] of longint;

n,a,b,i,m:integer;

r:longint;

//=======================================================================

function min(x,y:longint):longint;

begin

if x>y then exit(y);

exit(x);

end;

//=======================================================================

procedure dist;

var i,j,w,max,xx:longint;

begin

for i:=1 to n do

dis[i]:=map[1,i];

for i:=1 to n-1 do

begin

max:=0;

for j:=1 to n do

if not(v[j])and(dis[j]>max)

then begin

max:=dis[j];

w:=j;

end;

v[w]:=true;

for j:=1 to n do

begin

xx:=min(dis[w],map[w,j]);

if not(v[j])and(map[w,j]>0)and(xx>dis[j])

then dis[j]:=xx;

end;

end;

end;

//=======================================================================

procedure init;

begin

fillchar(map,sizeof(map),0); fillchar(v,sizeof(v),false);

readln(n);

repeat

readln(a,b,r); map[a,b]:=r

until (a=0)and(b=0)and(r=0);

end;

//=======================================================================

procedure print;

var i,j:longint;

begin

for i:=2 to n do

writeln(dis[i]);

end;

//=======================================================================

begin

assign(input,'in.txt');assign(output,'out.txt');

reset(input);rewrite(output);

init;

dist;

print;

close(input);close(output);

end.

大牛的思路：

好象没人用DIJSKTRA

其实用DIJSKTRA就行了

初始化dis[j]为g[1,j];

每次选出最大dis[k]

　　然后看是否能将其他的dis[j] 更新;

能更新的情况有

　　首先都要满足k到j有边(g[k,j]0);

然后:(1):当前没有路通向j(dis[j]=0);

　　　　(2):当前的dis[j]

最小最大问题

最短路算法的拓展