pypy3 解法, 执行用时: 3835ms, 内存消耗: 361156K, 提交时间: 2023-06-23 19:58:42

import heapq, math
import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n, m, s = map(int, input().split())
    routes = [[] for i in range(m)]
    g = [[] for i in range(n+1)]
    
    for i in range(m):
        a = list(map(int, input().split()))
        t = a[1]
        k = a[0]
        a = a[2:]
        for j in range(k-1):
            g[a[j]].append((a[j+1], j+1, t))
    
    dist = [float("inf")] * (n+1)
    dist[s] = 0
    q =[(0, s)]
    vis = [False] * (n+1)
    
    while q:
        d, ver = heapq.heappop(q)
        if vis[ver]: continue
        dist[ver] = d
        vis[ver] = True
        
        for u, x, y in g[ver]:
            if vis[u]: continue
            if d + 1 <= x:
                heapq.heappush(q, (x, u))
            else:
                heapq.heappush(q, (x + math.ceil((d+1-x)/y)*y, u))
    
    for i in range(1, n+1):
        if dist[i] == float("inf"): print(-1)
        else: print(dist[i])
        
    

C++(clang++ 11.0.1) 解法, 执行用时: 837ms, 内存消耗: 69700K, 提交时间: 2023-06-23 22:30:31

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
#define int long long
typedef pair<int, int> PII;
using node=tuple<int,int,int> ;
int n,m,s;
vector<node> g[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        int k,t;cin>>k>>t;
        vector<int> c(k);
        for(auto&x:c) cin>>x;
        for(int i=1;i<k;i++){
            g[c[i-1]].emplace_back(c[i],t,i-1);
        }
    }
    vector<int> d(n+1,-1);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({d[s]=0,s});
    while(q.size()){
        auto p=q.top();
        q.pop();
        int u=p.second;
        if(p.first>d[u]) continue;
        for(auto [v,t,m]:g[u]){
            int w=d[u]<=m?m:(d[u]-m+t-1)/t*t+m;
            w++;
            if(d[v]==-1||d[v]>w){
                q.push({d[v]=w,v});
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<d[i]<<"\n";
}

C++(g++ 7.5.0) 解法, 执行用时: 852ms, 内存消耗: 61720K, 提交时间: 2023-06-24 15:32:42

#include<bits/stdc++.h>

#define int long long
using namespace std;
using pii = pair<int, int>;

void solve() {
	int n, m, s;
	cin >> n >> m >> s;

	vector g(n + 5, vector<tuple<int, int, int>>());
	while (m --) {
		int k, t;
		cin >> k >> t;

		vector a(k, 0LL);
		for (int i = 0; i < k; i += 1) {
			cin >> a[i];
		}

		for (int i = 0; i + 1 < k; i += 1) {
			g[a[i]].emplace_back(a[i + 1], t, i);
		}
	}

	vector d(n + 5, - 1LL);
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.emplace(d[s] = 0, s);

	while (!q.empty()) {
		int u = q.top().second;
		q.pop();

		for (auto [v, t, i] : g[u]) {
			int w = max(d[u] - i + t - 1, 0LL) / t * t + i;
			w += 1;

			if (d[v] == - 1 || d[v] > w) {
				q.emplace(d[v] = w, v);
			}
		}
	}

	for (int i = 1; i <= n; i += 1) {
		cout << d[i] << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T --) {
		solve();
	}
}