QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#51491#4479. SlipperWinnerWA 1835ms221496kbC++111.9kb2022-10-02 15:18:312022-10-02 15:18:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-02 15:18:31]
  • 评测
  • 测评结果:WA
  • 用时:1835ms
  • 内存:221496kb
  • [2022-10-02 15:18:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, int> PLI;
typedef pair<int, ll> PIL;
#define x first
#define y second
const int N = 2e6 + 20;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
int n, k, p, s, t, maxd, depth[N];
vector<PII> node[N];
ll dis[N];
bool vis[N];

void init(){
    maxd = 0;
    for(int i = 1; i <= 2 * n; i++){
        node[i].clear();
    }
}

void dfs(int u, int fa, int d){
    depth[u] = d;
    for(auto [v, w]: node[u]){
        if(v == fa) continue;
        dfs(v, u, d + 1);
    }
    node[n + d].push_back({u, 0});
    node[u].push_back({n + d, 0});
    maxd = max(maxd, n + d);
}

void dijkstra(){
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    priority_queue<PLI, vector<PLI>, greater<PLI> > q;
    dis[s] = 0;
    q.push({0, s});
    while(!q.empty()){
        auto it = q.top();
        q.pop();
        ll nowdis = it.x;
        int nowid = it.y;
        if(vis[nowid]) continue;
        vis[nowid] = true;
        for(auto [v, w]: node[nowid]){
            if(vis[v]) continue;
            if(dis[nowid] + w < dis[v]){
                dis[v] = min(dis[v], dis[nowid] + w);
                q.push({dis[v], v});    
            }
        }
    }
}

void solve(){
    scanf("%d", &n);
    init();
    for(int i = 1; i < n; i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        node[u].push_back({v, w});
        node[v].push_back({u, w});
    }
    dfs(1, -1, 1);
    scanf("%d%d", &k, &p);
    for(int i = 1; i <= n; i++){
        if(n + i + k > maxd)
            break;
        node[n + i].push_back({n + i + k, p});
        node[n + i + k].push_back({n + i, p});
    }
    scanf("%d%d", &s, &t);
    dijkstra();
    printf("%lld\n", dis[t]);
}

int main(){
    int T = 1;
    scanf("%d", &T);
    while(T--){
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1835ms
memory: 221496kb

input:

5
121753
103252 40559 325002
32674 51809 946614
18343 12099 625962
27677 48601 114048
11146 12478 906161
121147 77390 208299
39512 95642 154696
90603 43508 378490
4829 7818 191754
73699 31412 536840
106916 89894 374802
113739 90049 411062
113123 73246 740213
38047 120942 903325
51907 41500 822541
90...

output:

243617
160058
94669
17377950755
51996

result:

wrong answer 1st lines differ - expected: '114128108', found: '243617'