QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#593090 | #6845. Tax | Sound_Medium | WA | 0ms | 3624kb | C++23 | 1.4kb | 2024-09-27 11:32:08 | 2024-09-27 11:32:09 |
Judging History
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'