54 条题解
-
1niujinyu 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; }
-
02016-08-19 09:57:50@
和丛林探险挺像的
#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;
} -
02016-07-13 22:54:35@
第二个点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.
我在秋名山等你!!!
-
02012-10-11 15:08:42@
8 10 10 120
1 2 2 1
1 3 1 1
1 4 2 19
2 3 2 6
3 4 1 1
3 5 2 2
5 6 2 1
6 7 1 3
7 8 3 1
4 8 7 100 -
02009-11-09 22:14:31@
被埋没的水题?
普通的dfs,弱弱的剪枝能过的。 -
02009-11-09 15:50:27@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms给题目害死了,
先看成有向图做,50分
结果发现了以后就改了读入时候的表,DFS里的没改
333333333333333333333333333333333次啊!! -
02009-11-05 07:59:39@
我写成了最大时间~ 囧~
MS很水的,不用spfa预处理搜索都可以~ -
02009-11-05 06:55:54@
有重边没~?
-
02009-11-03 23:30:46@
每条边只能走一次和每个点只能走一次不一样......
-
02009-10-31 15:07:17@
一开始时写着写着竟写成了最少钱数了……
对自己无语了…… -
02009-10-26 20:37:51@
先预处理,
分别计算出从n出发到每个点所需的
最短时间dt[i]和最少费用dv[i]
设当前剩余费用为v0,经过的时间t0如果出现以下两种情况则剪枝
1. dt[i]+t0>t
2. dv[i]+v0 -
02009-09-15 23:54:48@
编译通过...
├ 测试数据 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 -
02009-09-14 21:34:00@
-
02009-09-11 18:15:21@
编译通过...
├ 测试数据 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!
-
02009-08-27 11:21:51@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msSPFA预处理还真好用。
-
02009-08-10 19:25:32@
有点水的
很基础的搜索,连剪枝都不用的,可以用邻接矩阵优化的。 -
02009-08-04 12:48:01@
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 -
02009-07-31 15:43:33@
101题……
一个回文数…… -
02009-07-22 23:58:19@
题目难点在can't怎么打
writeln('can''t'); -
02009-06-19 22:26:57@
program p1399;
var m,n,p,q,i,j,k,l,r,t,ts,v,maxmo,mint,mote,tte:longint;
b:array[0..100,0..100]of longint;
mo:array[0..100,0..100]of longint;
tt:array[0..100,0..100]of longint;
map:array[0..100,0..100] of boolean;
procedure depe;
begin
if (mote>maxmo) and (mote