54 条题解
-
1
niujinyu LV 10 @ 2022-07-20 15:39:00
#include <cstdio> #include <queue> #include <algorithm> using std::max; using std::min; struct edge{ int v,T,M; edge *link; }; int n,m,top=0,TIME,MONEY; edge graph[110]={0}; edge node[100*100*2+100]; void add(int u,int v,int T,int M){ edge *l=&node[top++]; l->v=v,l->T=T,l->M=M; l->link=graph[u].link; graph[u].link=l; } void build(){ scanf("%d%d%d%d",&n,&m,&TIME,&MONEY); for(int i=1;i<=m;i++){ int u,v,T,M; scanf("%d%d%d%d",&u,&v,&T,&M); add(u,v,T,M); add(v,u,T,M); } } //DFS int vis[110][110]={0}; int bestT=999999999,bestM=0; void dfs(int u,int time,int money){ if(money>MONEY||time>TIME) return; if(u==n){ if(money>=bestM){ if(money==bestM) bestT=min(bestT,time); else bestT=time; bestM=money; } return; } edge *l=graph[u].link; while(l){ int v=l->v; if(!vis[u][v]){ vis[u][v]=vis[v][u]=1; dfs(v,time+l->T,money+l->M); vis[u][v]=vis[v][u]=0; } l=l->link; } } int main(){ freopen("in.txt","r",stdin); build(); dfs(1,0,0); printf("%d %d",bestT,MONEY-bestM); return 0; } -
0
和丛林探险挺像的
#include <cstdio>
#include <queue>struct edge{
int v,t,m;
edge *link;
};edge graph[110]={0};
edge node[101*101*2];
int n,m,T,V,top=0;void add(int u,int v,int t,int m){
edge*l=&node[top++];
l->v=v,l->t=t,l->m=m;
l->link=graph[u].link;
graph[u].link=l;
}int ans=-1,best=999999;
//SPFA
std::queue<int> q;
int inque[101]={0};
int dist[101];void spfa(int u){
for(int i=1;i<=n;i++)
dist[i]=99999999;
dist[u]=0;
q.push(u),inque[u]=0;
int t;
edge *l;
while(!q.empty()){
t=q.front();
q.pop(),inque[t]=0;
l=graph[t].link;
while(l){
if(dist[t]+l->t<dist[l->v]){
dist[l->v]=dist[t]+l->t;
if(!inque[l->v]){
q.push(l->v);
inque[l->v]=1;
}
}
l=l->link;
}
}
}//DFS
int vis[101][101]={0};void dfs(int u,int time,int money){
if(dist[u]>(T-time)||money>V)
return; //可行性剪枝
if(u==n){
if(ans<money)
ans=money,best=time;
else if(ans==money)
best=best<time?best:time;
return;
}
edge *l=graph[u].link;
while(l){
if(vis[u][l->v]==0){
vis[u][l->v]=vis[l->v][u]=1;
dfs(l->v,time+l->t,money+l->m);
vis[u][l->v]=vis[l->v][u]=0;
}
l=l->link;
}
}int main(){
#ifdef DEBUG
freopen("in.txt","r",stdin);
#endif
scanf("%d%d%d%d",&n,&m,&T,&V);
for(int i=1;i<=m;i++){
int q1,q3,q2,q4;
scanf("%d%d%d%d",&q1,&q2,&q3,&q4);
add(q1,q2,q3,q4);
add(q2,q1,q3,q4);
}
spfa(n);
dfs(1,0,0);
printf("%d %d",best,V-ans);
return 0;
} -
0
第二个点WA？！！ 我只想说...*每条路只能走一次* 和*每个点只能走一次是不一样的* ╮(╯▽╰)╭
测试数据 #0: Accepted, time = 0 ms, mem = 1672 KiB, score = 25
测试数据 #1: Accepted, time = 0 ms, mem = 1676 KiB, score = 25
测试数据 #2: Accepted, time = 0 ms, mem = 1672 KiB, score = 25
测试数据 #3: Accepted, time = 0 ms, mem = 1676 KiB, score = 25
Accepted, time = 0 ms, mem = 1676 KiB, score = 100pascal code
type int=longint; var n,m,t,v,k,max,min,a,b,c,d,i:int; w:array[0..101,0..101]of boolean; wt,wv:array[0..101,0..101]of int; time,value:array[0..100000]of int; procedure dfs(x,y,z:int); var i:int; begin if x=n then begin inc(k); time[k]:=t-y; value[k]:=v-z; exit; end; for i:=1 to n do if w[x,i] and (y>=wt[x,i]) and (z>=wv[x,i]) then begin w[x,i]:=false; w[i,x]:=false; dfs(i,y-wt[x,i],z-wv[x,i]); w[x,i]:=true; w[i,x]:=true; end; end; begin readln(n,m,t,v); k:=0; fillchar(w,sizeof(w),false); for i:=1 to m do begin readln(a,b,c,d); w[a,b]:=true; w[b,a]:=true; wt[a,b]:=c; wt[b,a]:=c; wv[a,b]:=d; wv[b,a]:=d; end; dfs(1,t,v); max:=0; for i:=1 to k do if value[i]>max then max:=value[i]; min:=maxlongint; for i:=1 to k do if (value[i]=max) and (time[i]<min) then min:=time[i]; writeln(min,' ',v-max); end.我在秋名山等你！！！
-
0
SecretAgent LV 10 @ 2009-10-26 20:37:51
先预处理，
分别计算出从n出发到每个点所需的
最短时间dt[i]和最少费用dv[i]
设当前剩余费用为v0，经过的时间t0如果出现以下两种情况则剪枝
1. dt[i]+t0>t
2. dv[i]+v0 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msprogram v1399;
var g:array[0..101,0..101,0..1] of longint;
i,j,n,t,w,t1,w1,m,x,y:longint;
can:array[1..100,1..100] of boolean;
procedure search(i,tx,wx:longint);
var j,c,d:longint;
begin
if i=n
then begin
if (tx>t)or(wx -
0
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msfor i := 1 to road[rnow,0] do
if not visit[rnow,road[rnow,i]] then
begin
visit[rnow,road[rnow,i]] := true;
visit[road[rnow,i],rnow] := true;
dfs(road[rnow,i],tnow+time[rnow,i],cnow+cost[rnow,i]);
visit[rnow,road[rnow,i]] := false;
visit[road[rnow,i],rnow] := false;
end;SO EASY!
-
0
peng7621260 LV 9 @ 2009-08-27 11:21:51
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msSPFA预处理还真好用。
-
0
var x,y,z,i,j,k,m,n,t1,m1:longint;
ok:array[0..201,0..201]of boolean;
time,money,t0,m0:longint;
a:array[0..201,0..201]of longint;
c,t:array[0..201,0..201]of longint;
s:array[0..201]of longint;
procedure dfs(v:longint);
var i,j:longint;
begin
if v=n then
begin
if m0>money then
begin
money:=m0;
time:=t0;
end
else if m0=money then
if t0 -
0
EZ_ray040123 LV 10 @ 2009-07-22 23:58:19
题目难点在can't怎么打
writeln('can''t');
niujinyu
LV 10
@ 2022-07-20 15:39:00
