QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#60665#4479. SlipperqinjianbinAC ✓826ms146296kbC++6.0kb2022-11-05 23:06:542022-11-05 23:06:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-05 23:06:56]
  • 评测
  • 测评结果:AC
  • 用时:826ms
  • 内存:146296kb
  • [2022-11-05 23:06:54]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<bitset>
#include<functional>
using namespace std;
//STL库常用(vector, map, set, pair)
#define pii pair<long long,int>
#define pdd pair<double,double>
#define F first
#define S second
//常量
#define PI (acos(-1.0))
#define INF 0x3f3f3f3f3f3f3f3f
//必加
#ifdef TanJI
#include<cassert>
#define dbg(...) do {cerr << #__VA_ARGS__ << " -> "; err(__VA_ARGS__); } while(0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A> void err(T<t> a, A... x) {for (auto v: a) cerr << v << ' '; cerr << ", "; err(x...);}
template<typename T, typename... A> void err(T a, A... x) {cerr << a << ' '; err(x...);}
template<typename T> void err(T *a, int len) {for (int i = 0; i < len; i++) cerr << a[i] << ' '; err();}
#else 
#define dbg(...)
#define assert(...)
#endif
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
// 快读快输
template<typename T> inline T read() {T x=0; bool f=0; char c=getchar();while(!isdigit(c)){if(c =='-')f= 1; c=getchar();}while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return f?~x+1:x;}
template<typename T> inline void print(T k){ int num = 0,ch[20]; if(k == 0){ putchar('0'); return ; } (k<0)&&(putchar('-'),k = -k); while(k>0) ch[++num] = k%10, k /= 10; while(num) putchar(ch[num--]+48); }
//图论
const int GRAPHN = 2e6 + 10, GRAPHM = 5e6 + 10;
int h[GRAPHN], e[GRAPHM], ne[GRAPHM], wei[GRAPHM], idx;
void AddEdge(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
void AddEdge(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], wei[idx] = c, h[a] = idx++;}
void AddEdge(int h[], int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
void AddEdge(int h[], int a, int b, int c) {e[idx] = b, ne[idx] = h[a], wei[idx] = c, h[a] = idx++;}
// 数学公式
template<typename T> inline T gcd(T a, T b){ return b==0 ? a : gcd(b,a%b); }
template<typename T> inline T lowbit(T x){ return x&(-x); }
template<typename T> inline bool mishu(T x){ return x>0?(x&(x-1))==0:false; }
template<typename T1,typename T2, typename T3> inline ll q_mul(T1 a,T2 b,T3 p){ ll w = 0; while(b){ if(b&1) w = (w+a)%p; b>>=1; a = (a+a)%p; } return w; }
template<typename T,typename T2> inline ll f_mul(T a,T b,T2 p){ return (a*b - (ll)((long double)a/p*b)*p+p)%p; }
template<typename T1,typename T2, typename T3> inline ll q_pow(T1 a,T2 b,T3 p){ ll w = 1; while(b){ if(b&1) w = (w*a)%p; b>>=1; a = (a*a)%p;} return w; }
template<typename T1,typename T2, typename T3> inline ll s_pow(T1 a,T2 b,T3 p){ ll w = 1; while(b){ if(b&1) w = q_mul(w,a,p); b>>=1; a = q_mul(a,a,p);} return w; }
template<typename T> inline ll ex_gcd(T a, T b, T& x, T& y){ if(b == 0){ x = 1, y = 0; return (ll)a; } ll r = ex_gcd(b,a%b,y,x); y -= a/b*x; return r;/*gcd*/ }
template<typename T1,typename T2> inline ll com(T1 m, T2 n) { int k = 1;ll ans = 1; while(k <= n){ ans=((m-k+1)*ans)/k;k++;} return ans; }
template<typename T> inline bool isprime(T n){ if(n <= 3) return n>1; if(n%6 != 1 && n%6 != 5) return 0; T n_s = floor(sqrt((db)(n))); for(int i = 5; i <= n_s; i += 6){ if(n%i == 0 || n%(i+2) == 0) return 0; } return 1; }
/* ----------------------------------------------------------------------------------------------------------------------------------------------------------------- */

const int MAXN = 2e6 + 10;
int T;
int n, k, p;
int cnt;
int s, t;

bool vis[MAXN];
int dep[MAXN];
vector<int> dv[MAXN];

ll dist[MAXN];
void dijk(int start) {
    for (int i = 1; i <= n; i++) vis[i] = false, dist[i] = INF;
    priority_queue<pii, vector<pii>, greater<pii> > que;
    dist[start] = 0;
    que.push(make_pair(0, start));
    while (que.size()) {
        int u = que.top().second; que.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i], c = wei[i];
            if (!vis[v] && dist[v] > dist[u] + c) {
                dist[v] = dist[u] + c;
                que.push(make_pair(dist[v], v));
            }
        }
    }

}

int main() {
#ifdef TanJI
    clock_t c1 = clock();
    freopen("D:\\Cpp\\1.in", "r", stdin);
    freopen("D:\\Cpp\\1.out", "w", stdout);
#endif
//--------------------------------------------
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int u, v, w;
        for (int i = 1; i <= n; i++) h[i] = -1; idx = 0;
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &u, &v, &w);
            AddEdge(u, v, w);
            AddEdge(v, u, w);
        }
        scanf("%d%d%d%d", &k, &p, &s, &t);
        for (int i = 0; i <= n; i++) dv[i].clear();
        for (int i = 1; i <= n; i++) vis[i] = false;
        queue<int> que;
        que.push(1);
        dv[0].push_back(1);
        int MH = 0;
        while (que.size()) {
            int u = que.front(); que.pop();
            vis[u] = true;
            for (int i = h[u]; ~i; i = ne[i]) {
                int v = e[i];
                if (vis[v]) continue;
                dep[v] = dep[u] + 1;
                MH = max(MH, dep[v]);
                dv[dep[v]].push_back(v);
                que.push(v);
            }
        }
        int cnt = n;
        for (int i = 0; i <= MH; i++) {
            cnt++;
            h[cnt] = -1;
            for (auto u: dv[i]) 
                AddEdge(u, cnt, 0);
            if (i + k <= MH) 
                for (auto u: dv[i + k]) 
                    AddEdge(cnt, u, p);
            if (i - k >= 0) 
                for (auto u: dv[i - k]) 
                    AddEdge(cnt, u, p);
        }
        n = cnt;
        dbg(s, t);
        dijk(s);
        printf("%lld\n", dist[t]);
    }
//--------------------------------------------    
#ifdef TanJI
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 826ms
memory: 146296kb

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:

114128108
55207815
76620494
17377950755
67601

result:

ok 5 lines