题解 - Vijos

3

PowderHan LV 10 @ 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;
}*/

Orina_zju @ 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
nmor @ 2019-09-07 23:38:50

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

1

天神塞勒涅 LV 10 @ 2018-04-18 17:36:09

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

1

larryzhong LV 9 @ 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

最强王者 LV 8 @ 2021-11-17 12:36:57

#include<bits/stdc++.h>
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;
}*/

0

Goodhao LV 10 @ 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

zhumingjie10 LV 8 @ 2012-11-03 21:45:56

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

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

0

Jormungand LV 5 @ 2012-10-05 10:01:23

二分+SPFA

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

0

神犇 LV 10 @ 2012-08-09 16:48:21

前两个点超时后面全对

纠结了好久不知为何

再交一次

AC了。。

0

zhaicong123 LV 8 @ 2010-07-21 20:41:47

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

太诡异咯！！！

0

IAM_LEgend LV 7 @ 2009-11-09 21:55:18

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

DFS+剪枝

0

yzl609271536 LV 10 @ 2009-11-09 11:35:00

数据范围看错了

用了马甲

Wa 了好久

0

mintalfance LV 10 @ 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

Plam_gxy LV 10 @ 2009-11-04 16:30:19

我想问一下.

我只写了一次SPFA,

判断只写了

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

0

tothesummer LV 7 @ 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

18317an7 LV 10 @ 2009-11-01 19:32:24

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

0

mike_nzk LV 10 @ 2009-10-30 22:03:24

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

0

SecretAgent LV 10 @ 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

liangwen LV 7 @ 2009-10-21 21:40:43

谢大牛指导！！！！！！！！！！！！！！！！！！！！！！！

数据很弱的.....

0

Dark_sun LV 9 @ 2009-10-21 19:55:11

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

用前向星存储;

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

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

然后DFS;

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

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

0

zhanghanyuan LV 10 @ 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 前向星

题解

104 条题解

丛林探险

信息

状态

开发

支持

题解

104 条题解

丛林探险

信息

状态

开发

支持

还没有账户？

登录