98 条题解
-
0
j262492438 LV 3 @ 2008-08-05 09:31:16
为什么我的会超时
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
Bellman-ford+小优化
秒杀
可惜，比赛的时候竟然想到二分答案去了
结果TLE了大半
祭奠下............ -
0
lolanvImba LV 3 @ 2008-07-21 22:13:32
小杉想越狱..
-
-1
spfa
#include <cstdio>
#include <queue>
#include <algorithm>
#define O 2100
using std::min;
struct edge{
int v,val;
edge *link;
};int n,top=0;
edge graph[O]={0};
edge node[O*O];void add(int u,int v,int val){
edge *l=&node[top++];
l->v=v,l->val=val;
l->link=graph[u].link;
graph[u].link=l;
}void build(){
scanf("%d",&n);
int u,v,val;
do{
scanf("%d%d%d",&u,&v,&val);
add(u,v,val);
}while(u&&v&&val);
}//SPFA
std::queue<int> q;
int inque[O]={0};
int dist[O];void spfa(int u){
for(int i=2;i<=n;i++)
dist[i]=0;
dist[1]=99999999;
q.push(u),inque[u]=1;
while(!q.empty()){
int t=q.front();
q.pop(),inque[t]=0;
edge *l=graph[t].link;
while(l){
int z=min(l->val,dist[t]);
if(dist[l->v]<z){
dist[l->v]=z;
if(!inque[l->v]){
q.push(l->v);
inque[l->v]=1;
}
}
l=l->link;
}
}
}int main(){
freopen("in.txt","r",stdin);
build();
spfa(1);
for(int i=2;i<=n;i++)
printf("%d\n",dist[i]);return 0;
} -
-1
cdqzgxxqdql LV 10 @ 2016-11-15 20:05:10
普通spfa
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int head[2005],dis[2005],tov[2000005],nex[2000005];
int w[2000005],tot,judge[2005];
inline void add(int a,int b,int c)
{
tov[++tot]=b;
nex[tot]=head[a];
head[a]=tot;
w[tot]=c;
}
inline void spfa()
{
queue<int>q;
q.push(1);dis[1]=0x7f7f7f7f;
while(!q.empty())
{
int k=q.front();q.pop();
int t=head[k];judge[k]=0;
while(tov[t])
{
if(dis[tov[t]]<min(dis[k],w[t]))
{
dis[tov[t]]=min(dis[k],w[t]);
if(!judge[tov[t]])
{
q.push(tov[t]);
judge[tov[t]]=1;
}
}
t=nex[t];
}
}
}
int main()
{
int n;scanf("%d",&n);
while(1)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==0)break;
add(a,b,c);
}
spfa();
for(int i=2;i<=n;i++)
printf("%d\n",dis[i]);
}
-
-1
-
-1
spfa + 模拟链表存图
但不知道vijos现在为什么不让打close作为变量
#include
#include
#include
#include
#define maxn 2001
#define maxm 1000000
using namespace std;
int dis[maxn],f[maxm],head[maxn];
struct jj{
int u,v,cost,next;
}num[maxm];
int open,clos,s,n;void adds(int a,int b,int c)
{
num.u=a;
num.v=b;
num.cost=c;
num.next=head[a];
head[a]=s;
}int main()
{
int a,b,r;
memset(num,0,sizeof(num));
memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
memset(dis,0,sizeof(dis));
dis[1]=maxm;
s=0;
cin>>n;
while(scanf("%d%d%d",&a,&b,&r) && (a!=0 || b!=0 || r!=0))
{
s++;
adds(a,b,r);
}
clos=0;
open=1;
f[1]=1;
while(clos < open)
{
clos++;
for(int i=head[f[clos]];i;i=num[i].next)
{
if(dis[num[i].v] < min(dis[num[i].u],num[i].cost))
{
open++;
f[open]=num[i].v;
dis[num[i].v]=min(dis[num[i].u],num[i].cost);
}
}
}
for(int i=2;i -
-1
spfa
模拟链表~0MS 秒杀
一次打过~~~~~
var
e:array[0..1999010] of record t,w,l:longint; end;
p,a,l:array[0..2000] of longint;
v:array[0..2000] of boolean;
i,j,n,t,f,s:longint;
procedure add(x,y,w:longint);
begin
inc(s);
e.t:=y; e.l:=p[x]; e.w:=w;
p[x]:=s;
end;
begin
fillchar(e,sizeof(e),0);
fillchar(p,sizeof(p),0);
readln(n);
readln(i,j,t);
repeat add(i,j,t); readln(i,j,t); until i=0;
a[1]:=maxlongint; s:=1; f:=0; l[1]:=1;
repeat
f:=(f+1) mod n;
i:=l[f];
v[i]:=false;
j:=p[i];
while j0 do
begin
if a[i]>e[j].w then t:=e[j].w else t:=a[i];
if t>a[e[j].t] then
begin
a[e[j].t]:=t;
if not v[e[j].t] then
begin
s:=(s+1) mod n; l:=e[j].t; v[e[j].t]:=true;
end;
end;
j:=e[j].l;
end;
until f=s;
for i:=2 to n do writeln(a[i]);
end.
j262492438
LV 3
@ 2008-08-05 09:31:16
