QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#593090#6845. TaxSound_MediumWA 0ms3624kbC++231.4kb2024-09-27 11:32:082024-09-27 11:32:09

Judging History

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

  • [2024-09-27 11:32:09]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3624kb
  • [2024-09-27 11:32:08]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define PII pair<int,int>
int n, m;

void solve () {
    cin>>n>>m;
    vector<int>gs(m+1,0);
    vector<int>a(m+1,0);
    vector<vector<pair<int,int>>>g(n+1);
    for(int i=1;i<=m;i++)cin>>a[i];
    vector<int>dis(n+1,1e18);
    vector<int>cost(n+1,1e18);
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }    
    dis[1]=0;
    queue<int>q;
    // priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push(1);
    cost[1]=0;
    while(q.size()){
        auto u=q.front();
        q.pop();
        for(auto [v,w]:g[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    auto dfs=[&](auto &&self,int u,int dist)->void{
        {}
        for(auto [v,w]:g[u]){
            if(dist+1!=dis[v])continue;
            gs[w]++;
            if(cost[v]>cost[u]+gs[w]*a[w]){
                cost[v]=cost[u]+gs[w]*a[w];
            }
            self(self,v,dist+1);
            gs[w]--;
        }
    };
    dfs(dfs,1,0);
    for(int i=2;i<=n;i++){
        cout<<cost[i]<<"\n";
    }

}
signed main () {
    int T = 1; 
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //cin>>T;
    while (T --) solve ();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

5 6
1 8 2 1 3 9
1 2 1
2 3 2
1 4 1
3 4 6
3 5 4
4 5 1

output:

1
9
1
3

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

10 15
730 2163 6818 4647 9699 1037 2034 8441 2619 6164 464 4369 4500 6675 1641
1 6 2
3 6 1
3 2 1
9 2 2
7 3 1
6 5 1
5 3 2
3 10 1
10 2 2
5 10 1
8 2 2
9 8 1
7 4 2
4 5 2
4 10 2

output:

4353
2893
7219
2893
2163
4353
8679
8679
4353

result:

ok 9 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10 15
847 2302 8846 8055 585 6541 6493 7165 5376 8551 836 2993 2700 9323 5119
2 1 5
2 3 3
3 10 3
10 4 3
8 3 4
10 8 1
3 7 3
4 5 3
5 8 5
6 3 3
8 6 2
6 5 4
9 10 2
7 9 4
5 9 4

output:

585
9431
53661
18656
27123
27123
17486
29425
27123

result:

ok 9 lines

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3528kb

input:

20 30
4547 9278 5093 443 7292 7570 7138 9315 4114 723 9854 9584 294 1861 5478 2734 5967 7102 6137 9504 456 7980 9645 6571 336 5308 1035 8008 3128 4035
7 1 2
11 7 1
11 12 2
12 10 2
10 5 2
20 5 1
20 17 2
17 16 2
16 18 1
7 19 3
19 12 1
2 18 2
3 7 1
12 3 1
19 3 1
13 11 1
12 13 1
19 13 1
13 3 2
18 15 2
8...

output:

156984
13825
87491
41653
24011
9278
28012
37652
37474
13825
18918
18918
24557
156984
97137
69303
115325
14371
50747

result:

wrong answer 1st lines differ - expected: '166078', found: '156984'