第六届CCPC长春站热身赛-C

第六届CCPC长春站热身赛-C

十一月 08, 2020

(热身赛暂时没链接)

  • ##题意

给出一个n个点m条边的图

每条边表示u -> v 所需的时间 (小时)

某人驾车从s -> t 点 他一天最多能开15小时车

问他最少几天到达终点

  • 题解

直接当作最短路会产生问题

比如：

A->B->C->D-> E 每两点间需要7 h 则需要两天

A -> X -> X -> E 每两点需要9h 则需要三天

所以想到用bfs + 最短路

每次从某个点跑最短路Dij将 15个小时内能到达的所有点 压入queue

因为15个小时能跑到的最远点 对于天数而言是等距离的点

在bfs 时 则将队列头 (较早遍历的点) 弹出 以这个点为根 再次跑最短路Dij 更新下一个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define P pair<ll,ll>
const int Max=1e5+5;
const ll Mod=1e9+7;
const ll inf=0x3f3f3f3f;
vector<P>mp[Max];
ll dis[Max];
int day[Max];
bool vis[Max],vis2[Max];
ll version[Max];
ll curver = 1;
queue<int>qq;

void update(int now){
    if(version[now]<curver){
        vis[now] = 0;
        dis[now] = inf;
        version[now] = curver;
    }
}

/*
6 7
1 6
1 2 15
2 5 15
5 6 15
1 6 15
1 3 1
3 4 1
4 6 15
*/

void Dijkstar(int st){
    priority_queue<P,vector<P>,greater<P> >q;
    q.push({0,st});
    update(st);
    dis[st]=0;
    while(!q.empty()){
        auto temp=q.top();q.pop();
        int now=temp.second;
        update(now);
        if(vis[now])continue;
        vis[now]=1;
        cout<<">>>>>from: "<<now<<endl;
        for(auto i:mp[now]){
            int to=i.first;
            ll cost=i.second;
            update(to);
            /// 避免每次使用Dij都要初始化所有点memset 所以记录一个版本号
            /// 若当前点版本早于这次跑Dij的版本那么就初始化表示它是之前Dij使用过 此次未使用过
            /// 否则这个点的版本=这次跑Dij的版本那么就不初始化表示它正在被使用
            //cout<<"day:"<<day[to]<<" curday:"<<day[st]<<endl;
            if(day[to]<=day[st])continue;
            ///此处剪枝 将超过一天的 点 放到下次bfs 时用Dij更新
            if(dis[now]+cost<min(16ll,dis[to])){
                dis[to]=dis[now]+cost;
                /*
                cout<<"to: "<<to<<" "
                    <<dis[now]<<"+"<<cost<<"="<<dis[to]<<endl;
                */
                q.push({dis[to],to});
                qq.push(to);
                day[to]=day[st]+1;
            }
        }
    }
}

void bfs(int st){
    qq.push(st);dis[st]=0;
    memset(day,0x3f,sizeof day);
    day[st]=0;int lastday=-1;
    while(!qq.empty()){
        int now=qq.front();qq.pop();
        if(vis2[now])continue;
        vis2[now]=1;

        if(day[now]>lastday){
            //cout<<"xx"<<endl;
            //memset(dis,0x3f,sizeof dis);
        }
        curver++;
        Dijkstar(now);
        lastday=day[now];
    }
}

int main(){
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,k;
        cin>>u>>v>>k;
        mp[u].push_back({v,k});
        mp[v].push_back({u,k});
    }
    bfs(s);
    //for(int i=1;i<=n;i++)cout<<i<<" "<<dis[i]<<endl;
    cout<<day[t]<<endl;
}