分层图的四倍经验

做完冻结后在做这三道题，简直爆切，直接四倍经验\(STO\)。

飞行路线：

几乎跟冻结一模一样就不讲啦

#include <bits/stdc++.h>
using namespace std;
int n , m , k , ans = 0x3ffffff , s , ee;
int dis[10000010] , vis[10000010];
vector<pair<int , int> > e[1000010];
void work(){
    priority_queue<pair<int , int> > q; 
    memset(dis , 127 , sizeof(dis));
    dis[s + k * n] = 0;
    q.push(make_pair(0 , s + k * n));
    while(!q.empty()){
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < e[x].size(); i++){
            int nx = e[x][i].first , w = e[x][i].second;
            if(dis[nx] > dis[x] + w){
                dis[nx] = dis[x] + w;
                q.push(make_pair(-dis[nx] , nx));
            }
        }
    }
}
int main(){
    cin >> n >> m >> k >> s >> ee;
    s++ , ee++;
    for(int i = 1; i <= m; i++){
        int x , y , z;
        cin >> x >> y >> z;
        x++ , y++;
        e[x].push_back(make_pair(y , z));
        e[y].push_back(make_pair(x , z));
        for(int j = 1; j <= k; j++){
            e[x + j * n].push_back(make_pair(y + n * (j - 1) , 0));
            e[x + j * n].push_back(make_pair(y + n * j , z));
            e[y + j * n].push_back(make_pair(x + n * (j - 1) , 0));
            e[y + j * n].push_back(make_pair(x + n * j , z));
        }
    }
    work();
    for(int i = 0; i <= k; i++) ans = min(dis[ee + i * n] , ans);
    cout << ans;
    return 0;
}

Telephone Lines S：

这道题改了一点点，就是让你输出的是最长的一条电话线，在跑最短路的时候改一下就OK了：

#include <bits/stdc++.h>
using namespace std;
int n , m , k , ans = 0x3ffffff , s , ee;
int dis[10000010] , vis[10000010];
vector<pair<int , int> > e[1000010];
void work(){
    priority_queue<pair<int , int> > q; 
    memset(dis , 127 , sizeof(dis));
    dis[s + k * n] = 0;
    q.push(make_pair(0 , s + k * n));
    while(!q.empty()){
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < e[x].size(); i++){
            int nx = e[x][i].first , w = e[x][i].second;
            if(dis[nx] > dis[x] + w){
                dis[nx] = dis[x] + w;
                q.push(make_pair(-dis[nx] , nx));
            }
        }
    }
}
int main(){
    cin >> n >> m >> k >> s >> ee;
    s++ , ee++;
    for(int i = 1; i <= m; i++){
        int x , y , z;
        cin >> x >> y >> z;
        x++ , y++;
        e[x].push_back(make_pair(y , z));
        e[y].push_back(make_pair(x , z));
        for(int j = 1; j <= k; j++){
            e[x + j * n].push_back(make_pair(y + n * (j - 1) , 0));
            e[x + j * n].push_back(make_pair(y + n * j , z));
            e[y + j * n].push_back(make_pair(x + n * (j - 1) , 0));
            e[y + j * n].push_back(make_pair(x + n * j , z));
        }
    }
    work();
    for(int i = 0; i <= k; i++) ans = min(dis[ee + i * n] , ans);
    cout << ans;
    return 0;
}

Revamping Trails G：

也是很简单的，我就不水了：

#include <bits/stdc++.h>
using namespace std;
int n , m , k , ans = 0x3ffffff;
int dis[1000010] , vis[1000010];
vector<pair<int , int> > e[1000010];
void work1(){
    priority_queue<pair<int , int> > q; 
    memset(dis , 127 , sizeof(dis));
    dis[1 + k * n] = 0;
    q.push(make_pair(0 , 1 + k * n));
    while(!q.empty()){
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < e[x].size(); i++){
            int nx = e[x][i].first , w = e[x][i].second;
            if(dis[nx] > dis[x] + w){
                dis[nx] = dis[x] + w;
                q.push(make_pair(-dis[nx] , nx));
            }
        }
    }
}
int main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int x , y , z;
        cin >> x >> y >> z;
        e[x].push_back(make_pair(y , z));
        e[y].push_back(make_pair(x , z));
        for(int j = 1; j <= k; j++){
            e[x + j * n].push_back(make_pair(y + n * (j - 1) , 0));
            e[x + j * n].push_back(make_pair(y + n * j , z));
            e[y + j * n].push_back(make_pair(x + n * (j - 1) , 0));
            e[y + j * n].push_back(make_pair(x + n * j , z));
        }
    }
    work1();
    for(int i = 0; i <= k; i++) ans = min(dis[n + i * n] , ans);
    cout << ans;
    return 0;
}