#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
const int maxV = 2020;
using std::vector;
using std::deque;
struct edge {
int w, t;
edge (int _t = 0, int _w = 0) {
w = _w;
t = _t;
}
};
int V;
int f[maxV];
bool vis[maxV];
vector<edge> s[maxV];
void init () {
int x, y, z;
scanf("%d %d %d %d", &V, &x, &y, &z);
while (x != 0 || y != 0 || z != 0) {
s[x].push_back(edge(y, z));
scanf("%d %d %d", &x, &y, &z);
}
}
inline int min (int a, int b) {
return (a < b ? a : b);
}
void spfa (int source) {
int cur, curTo, curW;
memset(f, 0, sizeof(f));
memset(vis, false, sizeof(vis));
deque<int> q;
q.push_back(source);
vis[source] = true;
f[source] = INT_MAX;
while (!q.empty()) {
cur = q.front();
q.pop_front();
vis[cur] = false;
for (int i = 0, size = s[cur].size(), t; i < size; ++i) {
curTo = s[cur][i].t;
curW = s[cur][i].w;
t = min(curW, f[cur]);
if (f[curTo] < t) {
f[curTo] = t;
if (!vis[curTo]) {
vis[curTo] = true;
q.push_back(curTo);
}
}
}
}
}
int main () {
init ();
spfa (1);
for (int i = 2; i <= V; ++i)
printf("%d\n", f[i]);
return 0;
}
相当简单的spfa

表示题目远远不如p1053
我刚做了1053于是改了改程序
AC
注意：可以照抄1053
1：数组要开到2000
2：不是输出nopath
3：把d[c[he]]+a[c[he],i,1]换成min(d[c[he]],a[c[he],i,1])
4：初始化时把其他赋成0，把1赋成maxlongint
5：去掉最小环
总体比1053简单多了

program p1391;
var
n,m,s,i,j,x,y,z,he,ti:longint;
a:array[1..2000,1..2000,0..1]of longint;
b,c,d,e,f:array[1..10000000]of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x);exit(y);
end;
procedure spfa(s:longint);
begin
fillchar(c,sizeof(c),0);e:=c;
for i:=1 to n do d[i]:=0;d[s]:=1000000000;
he:=0;ti:=1;c[1]:=s;
while he<ti do begin
inc(he);inc(e[he]);
for i:=1 to b[c[he]] do begin
if min(d[c[he]],a[c[he],i,1])>d[a[c[he],i,0]] then begin
d[a[c[he],i,0]]:=min(d[c[he]],a[c[he],i,1]);
inc(ti);c[ti]:=a[c[he],i,0];end;
end;
end;
end;
begin
readln(n);read(x,y,z);
while x<>0 do begin
inc(m);
inc(b[x]);a[x,b[x],0]:=y;a[x,b[x],1]:=z;read(x,y,z);end;
spfa(1);
for i:=2 to n do if d[i]<>0 then writeln(d[i])
else writeln(0);
end.

var
n,i,j,x,y,z,minx,linshi:longint;
a:array[1..2000,1..2000]of longint;
dis:array[1..2000]of longint;
b:array[1..2000]of boolean;
function min(a,b:longint):longint;
begin
if(a>b)then exit(b)
else exit(a);
end;
function max(a,b:longint):longint;
begin
if(a>b)then exit(a)
else exit(b);
end;
procedure init;
begin
readln(n);
for i:=1 to n do for j:=1 to n do a[i,j]:=-1;
readln(x,y,z);
while(x<>0)and(y<>0)and(z<>0)do
begin
a[x,y]:=z;
readln(x,y,z);
end;
end;
procedure main;
begin
for i:=1 to n do dis[i]:=-1;
fillchar(b,sizeof(b),false);
dis[1]:=maxlongint-1;
for i:=1 to n do
begin
minx:=-1;
x:=0;
for j:=1 to n do
if(dis[j]>minx)and(not b[j])then
begin
minx:=dis[j];
x:=j;
end;
if(x<>0)then
begin
b[x]:=true;
for j:=1 to n do
if(x<>j)and(a[x,j]<>-1)then
begin
linshi:=0;
linshi:=min(dis[x],a[x,j]);
dis[j]:=max(linshi,dis[j]);
end;
end;
end;
end;
procedure w;
begin
for i:=2 to n do if(dis[i]<>-1)then writeln(dis[i])
else writeln(0);
end;
begin
init;
main;
w;
end.
表示SPFA这么好用么= =

var
n,a,b,c,i,j,max,p:longint;
mp:array[0..2001,0..2001] of longint;
dist:array[0..2001] of longint;
f:array[0..2001] of boolean;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a)
end;
begin
readln(n);
repeat
readln(a,b,c);
mp[a,b]:=c;
until a=0;
for i:=1 to n do
if mp[1,i]>0 then dist[i]:=mp[1,i];
f[1]:=true;
for i:=1 to n-1 do
begin
max:=0;
for j:=1 to n do
if (f[j]=false) and (dist[j]>max) then
begin
max:=dist[j];
p:=j;
end;
f[p]:=true;
for j:=1 to n do
if (f[j]=false) and (mp[p,j]>0) then
if min(mp[p,j],max)>dist[j] then//最短路的变形
dist[j]:=min(mp[p,j],max);
end;
for i:=2 to n do
writeln(dist[i]);
end.

走不到输出0——为此WA一次！

这题谁能提供一些数据，测试一下

0.0

dj

为什么交的第一遍全部超时。

spfa。数组开小了，于是干脆搞了个循环队列

不知道这样做好不好...

#include

int n;

long map[2001][2001]={0};

int mark[2001]={0};

long maxrp[2001]={0};

long min(long a,long b)

{return a

Dijstra能过否？。。。。

水题，最长路变种...

类似求最短路的算法，每次取出最大的dis[i]之后的松弛操作是更新可以通过的最大RP，不再是路径长度

const

ma=2000;

var

cost:array[1..ma,1..ma]of longint;

dist,q:array[1..ma]of longint;

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

n:longint;

procedure init;

var a,b,r:longint;

begin

readln(n);

while 1=1 do

begin

readln(a,b,r);

if (a=0)or(b=0) then break

else cost[a,b]:=r;

end;

end;

function min(i,j:longint):longint;

begin

if i=0 then min:=j else

if i0 then

begin

k:=min(dist[j],cost[j,i]);

if k>dist[i] then

begin

dist[i]:=k;

if not(v[i]) then

begin

v[i]:=true;

t:=t mod n+1;

q[t]:=i;

end;

end;

end;

end;

v[j]:=false;

end;

end;

procedure print;

var i:longint;

begin

for i:=2 to n do

writeln(dist[i]);

end;

begin

fillchar(cost,sizeof(cost),0);

init;

spfa;

print;

end.

数组开小了，提了N多次。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

悲剧了。交了3次。。

0分的注意 。走不到输出0.。。

什么玩艺啊?

怎么输入和输出描述一样啊？

spfa..

用最不优化的找点方法过的。。

这是一道好题！很经典的spfa变形（虽然第一次没看出来。。）。很显然可以得到从1到i的最优值dis[i]=max(min(dis[x],g[x,i]))，出现最大最小问题第一想法是二分。。但是当n高达2000还可能是完全图的情况下，二分判定很显然是会TLE的。。所以想到利用类似spfa的做法解决该问题，具体做法如下：

利用队列q中的元素不断的对dis[i]进行松弛，若i未出现在队列中，则入队列，判定更新条件为min(dis[x],g[x,i])>dis[i]，当队列为空时，可证全部松弛完毕，即dis[2..n]为所求答案，输出即可。

附上垃圾程序的核心部分：

while headdis[i] then

begin

dis[i]:=t;

if not v[i] then

begin

inc(tail);

q[tail]:=i;

v[i]:=true;

end;

end;

end;

v[x]:=false;

inc(head);

end;

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

裸SPFA。。。几乎没秒杀。。囧

sunny机交900+ms

puppy机交0ms

同样是裸的spfa差距怎么就这么大。。。。

Unaccepted 有效得分：80 有效耗时：379ms

Dijkstra寻找最大值时初始化max=0......

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

试图改一下初始化max=-1.....

这到底怎么回事啊.....