L3-022 地铁一日游 (30 分)

题目描述：

n个点，m条道路，以及每k公里加一块钱车费,这里的规则是只有距离真正到达k，才会加钱，即40公里花4块钱，39公里花3元

你可以在任意一个站点上上下车换道路

他为了贪便宜，对于所有车费相同的到达站，森森只会在计费距离最远的站停下来，而且这里的距离是两个点之间的最短距离，也可以在道路的端点停下来

给你q次询问，每次询问，都问以x为起点的，能停留的点的集合是什么

思路：

最短路用floyed求

求出最短路后，我们重新建图，对于每个点i，点每个能到达的点j，设二者之间的最短距离是dis，我们可以计算出 $\frac{dis}{k}$作为他的花费，开一个map记录每种花费对应的最大距离，然后再扫一遍，判断哪些点能连边就连上

注意，因为可以在道路的终点站停下来，所以要记录一下道路的起点和终点，而不是根据原图的度来判！

建完新图以后，就可以写dfs去跑，放set里面去重排序，输出就行

坑点：

• 车费的计算方式，是下取整，不是他妈的上取整
• 道路的端点是每条道路的端点，不是他妈的原图的叶子点
• 输入方式恶心的很

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 2000 + 50
int n, m, k, x, y, z, tot;
int tr[MAX];
string s;
bool G[MAX][MAX];
bool duan[MAX];
int dis[MAX][MAX];
void Floyed(){
    for(int i = 1; i <= n; ++i)dis[i][i] = 0;
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}
bool vis[MAX];
set<int>se;
void dfs(int u){
    vis[u] = 1;
    se.insert(u);
    for(int v = 1; v <= n; ++v){
        if(!vis[v] && G[u][v]){
            dfs(v);
        }
    }
}

void work(){
    cin >> n >> m >> k;
    mem(dis, inf);
    getchar();
    for(int i = 1; i <= m; ++i){
        getline(cin, s);
        stringstream ss;
        ss << s;
        tot = 0;
        while (ss >> s) {
            tr[++tot] = stoi(s);
        }
        for(int i = 1; i < tot; i += 2){
            x = tr[i];y = tr[i + 2];z = tr[i + 1];
            if(i == 1)duan[x] = 1;
            if(i == tot - 2)duan[y] = 1;
            dis[x][y] = dis[y][x] = min(dis[x][y], z);
        }
    }
    Floyed();
    for(int i = 1; i <= n; ++i){
        map<int, int>mp;
        for(int j = 1; j <= n; ++j){
            if(dis[i][j] == inf)continue;
            int p = dis[i][j] / k;
            mp[p] = max(mp[p], dis[i][j]);
        }
        for(int j = 1; j <= n; ++j){
            int p = dis[i][j] / k;
            if(i == j || dis[i][j] == inf)continue;
            if(duan[j] || dis[i][j] == mp[p])G[i][j] = 1;
        }
        G[i][i] = 1;
    }
    cin >> m;
    while (m--) {
        mem(vis, 0);se.clear();
        cin >> x;
        dfs(x);
        cout << *se.begin();
        se.erase(*se.begin());
        for(auto x : se){
            cout << " " << x ;
        }
        cout << endl;
    }
}


int main(){
    work();
    return 0;
}