QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#51471 | #4479. Slipper | zzxzzx123 | WA | 1984ms | 219464kb | C++17 | 1.8kb | 2022-10-02 14:53:25 | 2022-10-02 14:53:29 |
Judging History
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;
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){
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(nowdis + w < dis[v]){
dis[v] = min(dis[v], nowdis + 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 = n+1; i+k <= maxd; i++){
node[ i].push_back({ i + k, p});
node[i + k].push_back({ 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: 1984ms
memory: 219464kb
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'