题解

103 条题解

  • 3
    @ 2017-05-07 22:40:05
    /*
    也算是一种题型了吧
    SPFA多了一个约束条件即体力值要满足
    一个可行法是
    写3个SPFA,一个来判最短体力是否大于k,一个来判最短时间,然后二分再SPFA
    看到题解区有一种这样的做法
    在SPFA的时候多加一个条件:当前体力花费<=k,一次SPFA跑完
    这样其实仔细想是错误的贪心法
    可能你节约的时间会让你的体力无法到达
    但是竟然神奇地也能AC(数据奇水)
    比如我们有数据
    4 4
    1 3 5 2
    1 2 1 2
    2 3 2 2
    3 4 2 1
    1 4
    6
    答案是5但是如果用上面的贪心会是-1
    正解应该是
    直接跑两遍最短路,然后将所有可以用的边全部找出来,然后在跑一遍最短路求出最短时间即可
    http://blog.csdn.net/dan__ge/article/details/52529145
    但是看到数据范围其实并不大
    完全可以搜索bfs或者dfs解决
    我这里用的dfs很方便
    直接深搜加入当前节点和当前所用时间以及所用体力为参数
    加入剪枝
    1.可行性剪枝havec>k return
    2.最优性剪枝havet>ans(当前的最优可行时间) return
    这样时间复杂度O(n+m)并且剪枝了
    所以必然还是很快的
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=5005;
    const int MAXM=40005;
    const int INF=(1<<30)-1;
    struct Edge
    {
        int to,c,t,next;
    }e[MAXM<<1];
    int fisrt[MAXN];
    bool vis[MAXN];
    int n,m,tot,k;
    int s,t;
    int ans=INF;
    
    inline void Add_Edge(int& x,int& y,int& c,int& t)
    {
        e[++tot].to=y;  e[tot].c=c; e[tot].t=t;
        e[tot].next=fisrt[x];   fisrt[x]=tot;
    }
    
    void init()
    {
        memset(fisrt,-1,sizeof(fisrt));
        scanf("%d%d",&n,&m);
        int x,y,c,t1;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&x,&y,&c,&t1);
            Add_Edge(x,y,c,t1);  Add_Edge(y,x,c,t1);
        }
        scanf("%d%d%d",&s,&t,&k);
        vis[s]=1;
    }
    
    void dfs(int u,int havec,int havet)
    {
        if(havec>k||havet>ans)
            return;
        if(u==t)
        {
            ans=min(ans,havet);
            return;
        }
        for(int i=fisrt[u];i!=-1;i=e[i].next)
        {
            int& v=e[i].to; int& c=e[i].c;  int& t=e[i].t;
            if(!vis[v])
            {
                vis[v]=1;
                dfs(v,havec+c,havet+t);
                vis[v]=0;
            }
        }
    }
    
    void out()
    {
        if(ans==INF)
            printf("-1\n");
        else
            printf("%d\n",ans);
    }
    
    int main()
    {
        init();
        dfs(s,0,0);
        out();
    }
    
    /*#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=5005;
    const int MAXV=400005;
    const int INF=0x7fffff;
    struct node
    {
        int to,next,w,c;
        node()
        {
            to=next=-1;
            w=c=0;
        }
    }e[MAXV];
    int fisrt[MAXN];
    int q[MAXN+5];
    bool in[MAXN];
    int d[MAXN];
    int c[MAXN];
    int front,rear;
    int n,m;
    int s,t;
    int tot;
    int k;
    
    void inline Add_Edge(int x,int y,int w,int c)
    {
        tot++;
        e[tot].to=y;
        e[tot].w=w;
        e[tot].c=c;
        e[tot].next=fisrt[x];
        fisrt[x]=tot;
    }
    
    void init()
    {
        int x,y,w,c;
        cin>>n>>m;
        memset(fisrt,-1,sizeof(fisrt));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y>>c>>w;
            Add_Edge(x,y,w,c);
            Add_Edge(y,x,w,c);
        }
        cin>>s>>t;
        cin>>k;
        for(int i=1;i<=n;i++)
            d[i]=INF;
    }
    
    bool SPFA(int s)
    {
        d[s]=0;
        in[s]=1;
        q[rear++]=s;
        while(front!=rear)
        {
            int x=q[front];
            front=(front+1)%MAXN;
            in[x]=0;
            for(int i=fisrt[x];i!=-1;i=e[i].next)
            {
                int u=e[i].to; int w=e[i].w;   int c1=e[i].c;
                if(d[x]+w<d[u]&&c[x]+c1<=k)
                {
                    d[u]=d[x]+w;
                    c[u]=c[x]+c1;
                    if(!in[u])
                    {
                        q[rear]=u;
                        rear=(rear+1)%MAXN;
                        in[u]=1;
                    }
                }
            }
        }
        return d[t]!=INF;
    }
    
    int main()
    {
        init();
        if(SPFA(s))
            cout<<d[t]<<endl;
        else
            cout<<-1<<endl;
        return 0;
    }*/
    
    
    • @ 2017-07-13 23:59:21

      3遍最短路的那个解法似乎有问题,看一下这组数据:
      (正确答案应该是1001,但用3遍最短路算出来的是7)
      8 17
      1 2 8 1
      2 3 8 1
      3 4 8 1
      4 5 8 1
      5 6 8 1
      6 7 8 1
      7 8 8 1
      1 3 1 1000
      1 4 1 1000
      1 5 1 1000
      1 6 1 1000
      1 7 1 1000
      2 8 1 1000
      3 8 1 1000
      4 8 1 1000
      5 8 1 1000
      6 8 1 1000
      1 8
      10

    • @ 2019-09-07 23:38:50

      起点到U和从终点到V都是选的最小体力才判断边是否可以走,然而实际上不一定是

  • 1
    @ 2018-04-18 17:36:09

    FFFFFFUCK!!!
    2,3点TLE了N次。。。
    忘了大于当前最优解也要剪枝

  • 1
    @ 2017-10-02 12:08:01

    Dijkstra 算法,更新注意一下就行了(注:这题数据有点水)

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 5010, INF = 0x3f3f3f3f;
    int n, m, s, t, _max, add[maxn][maxn], cost[maxn][maxn], used[maxn], tmp[maxn], d[maxn];
    
    int dijkstra() {
        fill(d + 1, d + n + 1, INF);
        fill(tmp + 1, tmp + n + 1, INF);
        d[s] = 0;
        tmp[s] = 0;
        while (true) {
            int u = -1;
            for (int v = 1; v <= n; v++) {
                if (!used[v] && (u == -1 || d[v] < d[u])) {
                    u = v;
                }
            }
            if (u == -1) {
                break;
            }
            used[u] = true;
            for (int v = 1; v <= n; v++) {
                if (tmp[u] + add[u][v] <= _max) {    // 重点
                    if (d[v] == d[u] + cost[u][v]) {
                        tmp[v] = min(tmp[v], tmp[u] + add[u][v]);
                    }
                    if (d[v] > d[u] + cost[u][v]) {
                        d[v] = d[u] + cost[u][v];
                        tmp[v] = tmp[u] + add[u][v];
                    }
                }
            }
        }
        return d[t];
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    cost[i][j] = INF;
                }
                if (i != j) {
                    add[i][j] = INF;
                }
            }
        }
        while (m--) {
            int u, v, c, d;
            cin >> u >> v >> c >> d;
            cost[u][v] = cost[v][u] = min(cost[u][v], d);
            add[u][v] = add[v][u] = min(add[u][v], c);
        }
        cin >> s >> t >> _max;
        int res = dijkstra();
        cout << (res == INF ? -1 : res) << endl;
        return 0;
    }
    
  • 0
    @ 2018-08-02 08:18:00

    本题是不是只能搜索啊?。。

    PowderHan提到的某博客中的最短路算法是错的,dis1和dis2同时满足两个约束不代表就一定存在一条路径能同时满足两个约束,可能是两条不同的路径分别满足了1个

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7777777;
    const double eps=1e-8;
    
    int n,m;
    int s,t,k;
    int ans=inf;
    struct edge {
        int to;
        int v1,v2;
    };
    vector<edge> g[5001];
    bool vis[5001];
    void dfs(int x,int time,int dis) {
        if (dis>ans) return;
        if (time>k) return;
        if (x==t) {
            ans=min(ans,dis);
            return;
        }
        for (int i=0;i<g[x].size();i++) {
            int y=g[x][i].to;
            int v1=g[x][i].v1;
            int v2=g[x][i].v2;
            if (vis[y]) continue; 
            vis[y]=1;
            dfs(y,time+v1,dis+v2);
            vis[y]=0;
        }
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>n>>m;
        FOR(i,m) {
            int x,y,c,d;
            cin>>x>>y>>c>>d;
            g[x].pb(edge{y,c,d});
            g[y].pb(edge{x,c,d});
        }
        cin>>s>>t>>k;
        vis[s]=1;
        dfs(s,0,0);
        vis[s]=0;
        if (ans==inf) cout<<-1<<endl;
        else cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2012-11-03 21:45:56

    额……本来还想用来做SPFA的练手题的,结果……由于可行性的限制,我们还是用DFS为妥。。

    至于数据的存储么。。。边写个struct挂个链就好~~~~

  • 0
    @ 2012-10-05 10:01:23

    二分+SPFA

    二分答案,再用SPFA判断在体力不超过K的前提下是否可行。

  • 0
    @ 2012-08-09 16:48:21

    前两个点超时后面全对

    纠结了好久不知为何

    再交一次

    AC了。。

  • 0
    @ 2010-07-21 20:41:47

    为什么我spfa 不用判断入队就可以AC,加了判断入队的语句反而WA了4组!!!

    太诡异咯!!!

  • 0
    @ 2009-11-09 21:55:18

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

    DFS+剪枝

  • 0
    @ 2009-11-09 11:35:00

    数据范围看错了

    用了马甲

    Wa 了好久

  • 0
    @ 2009-11-04 16:34:34

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    数据弱得很,用不着spfa,直接深搜。。

  • 0
    @ 2009-11-04 16:30:19

    我想问一下.

    我只写了一次SPFA,

    判断只写了

    if (t[o]+e[i].time

  • 0
    @ 2009-11-02 11:48:52

    谁帮我看看程序 两次spfa预处理加深搜 有两个点216错误?

    program p1;

    type

    gralist=^enode;

    enode=record

    adjv:0..5000;

    next:gralist;

    w1:longint;

    w2:longint;

    end;

    vnode=record

    link:gralist;

    end;

    adjlist=array[0..5000] of vnode;

    var n,e,head,tail,i,a,b,x,y,hp,short,s,t:longint;

    f,f1,list:array[0..5000] of longint;

    bool:array[0..5000] of boolean;

    g:adjlist;

    p:gralist;

    procedure search(k,cost,hp:longint);

    var p:gralist;

    begin

    if k=t then

    begin

    short:=cost;

    exit;

    end;

    p:=g[k].link;

    bool[k]:=true;

    while pnil do

    begin

    if (hp-(f1[p^.adjv]+p^.w2)>=0)and(cost+(f[p^.adjv]+p^.w1)

  • 0
    @ 2009-11-01 19:32:24

    反向两边SPFA+暴力Astar,以为会TLE,居然1Y

  • 0
    @ 2009-10-30 22:03:24

    碰到了Vijos Easy!!!没秒杀,而且是332ms!!!

  • 0
    @ 2009-10-23 15:35:48

    可行性剪枝+最优性剪枝

    可行:体力消耗完毕

    最优:当前以走的路程大于最优

    第一次没把邻接表做成双向,

    第二次没注意无解,可怜的AC率啊。。

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    • @ 2013-11-07 19:45:23

      正解,数据太弱了。。。

  • 0
    @ 2009-10-21 21:40:43

    谢大牛指导!!!!!!!!!!!!!!!!!!!!!!!

    数据很弱的.....

  • 0
    @ 2009-10-21 19:55:11

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

    用前向星存储;

    SPFA预处理,生成数组d,d[i]表示节点i到终点所消耗的最小体力值;

    若d[起点]>k,无解;

    然后DFS;

    一个可行性剪枝,若d[i]>剩余体力,则剪掉.

    一个最优性剪枝,若当前所耗时间>=min,则剪掉.

  • 0
    @ 2009-10-19 20:15:06

    编译通过...

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

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

    ├ 测试数据 03:鸢刚?.. 0ms

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

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

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

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

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

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

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

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

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

    ORZ 前向星

  • 0
    @ 2009-10-19 16:21:45

    7 10 WA了……

    囧……

信息

ID
1082
难度
7
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
2058
已通过
463
通过率
22%
被复制
2
上传者