题解 - 帖子

按 (时间，城市) 建图，则存在下面两种边，原问题就变为了 (0,s) 出发的单源最短路问题：

对所有时间 t，城市 v，连边，边权为 C，表示等待 1 份时间；
对所有航线，设其起点 u，终点 v，开点 st，到点 ed，票价 c，连边，边权，表示乘车。

不难发现可以只保留航线中用到的点（共个），而将第一类边合并，所以建图可以做到。

又发现边都是从时间小的连向时间大的，所以此图是 DAG，可以拓扑排序+dp 求最短路。由于时间顺序就是天然的拓扑序，所以每个时间开 vector 存更新，从早到晚处理时间时先生效 vector 中的更新，再将这一时刻出发的航线加入之后的时刻的更新中即可做到严格线性。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;

const int MAXT = 1000300;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
struct Edge {
    int b, e, s, t, c;
    void input() { cin >> s >> t >> b >> e >> c, s--, t--; }
};
void umin(ll &x, ll y) { if(y < x) x = y; }

int main() {
    ios::sync_with_stdio(false);
    ll n, m, o, A, B, C;
    cin >> n >> m >> o >> A >> B >> C, o--;
    vector<ll> dp(n, INFL), las(n, 0), ans(n, INFL); dp[o] = ans[o] = 0;
    vector< vector<pii> > updates(MAXT);
    vector< vector<Edge> > edges(MAXT);
    for(int i = 0; i < m; ++i) {
        static Edge e; e.input();
        edges[e.b].push_back(e);
    }
    for(int i = 0; i < MAXT; ++i) {
        for(auto [p, v] : updates[i]) {
            if(las[p] != i && dp[p] != INFL) dp[p] += C * (i - las[p]);
            umin(dp[p], v), umin(ans[p], dp[p]), las[p] = i;
        }
        for(auto e : edges[i]) if(dp[e.s] != INFL) {
            if(las[e.s] != i) dp[e.s] += C * (i - las[e.s]), las[e.s] = i;
            updates[e.e].emplace_back(e.t, dp[e.s] + A * e.c + B + C * (e.e - e.b));
        }
    }
    for(auto g : ans)
        cout << (g >= INFL ? -1 : g) << '\n';

    return 0;
}