54 条题解

  • 1
    @ 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
    @ 2016-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;
    }

  • 0
    @ 2016-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 = 100

    pascal 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
    @ 2012-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

  • 0
    @ 2009-11-09 22:14:31

    被埋没的水题?

    普通的dfs,弱弱的剪枝能过的。

  • 0
    @ 2009-11-09 15:50:27

    编译通过...

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

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

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

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

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

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

    给题目害死了,

    先看成有向图做,50分

    结果发现了以后就改了读入时候的表,DFS里的没改

    333333333333333333333333333333333次啊!!

  • 0
    @ 2009-11-05 07:59:39

    我写成了最大时间~ 囧~

    MS很水的,不用spfa预处理搜索都可以~

  • 0
    @ 2009-11-05 06:55:54

    有重边没~?

  • 0
    @ 2009-11-03 23:30:46

    每条边只能走一次和每个点只能走一次不一样......

  • 0
    @ 2009-10-31 15:07:17

    一开始时写着写着竟写成了最少钱数了……

    对自己无语了……

  • 0
    @ 2009-10-26 20:37:51

    先预处理,

    分别计算出从n出发到每个点所需的

    最短时间dt[i]和最少费用dv[i]

    设当前剩余费用为v0,经过的时间t0

    如果出现以下两种情况则剪枝

    1. dt[i]+t0>t

    2. dv[i]+v0

  • 0
    @ 2009-09-15 23:54:48

    编译通过...

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

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

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

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

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

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

    program 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
    @ 2009-09-11 18:15:21

    编译通过...

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

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

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

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

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

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

    for 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
    @ 2009-08-27 11:21:51

    编译通过...

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

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

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

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

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

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

    SPFA预处理还真好用。

  • 0
    @ 2009-08-10 19:25:32

    有点水的

    很基础的搜索,连剪枝都不用的,可以用邻接矩阵优化的。

  • 0
    @ 2009-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

  • 0
    @ 2009-07-31 15:43:33

    101题……

    一个回文数……

  • 0
    @ 2009-07-22 23:58:19

    题目难点在can't怎么打

    writeln('can''t');

  • 0
    @ 2009-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

信息

ID
1399
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
796
已通过
245
通过率
31%
被复制
3
上传者