UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214253#2763. 幻想乡的拜访tonysun053030295ms17860kbC++1.4kb2024-11-16 20:30:592024-11-16 23:12:41

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define PII pair<int, int>
#define int long long

using namespace std;

const int N = 1e6 + 10;
const int M = N << 1;
const int mod = 1e9 + 7;

int n;
int h[N], e[M], ne[M], w[N], idx;
int dist[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    heap.push({0, s});

    while (heap.size())
    {
        pair<int, int> t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + 1)
            {
                dist[j] = dist[ver] + 1;
                heap.push({dist[j], j});
            }
        }
    }
}

signed main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1 ; i < n ; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++ )
    {
        memset(st, 0, sizeof st);
        dijkstra(i);
        for(int j = 1 ; j < i ; j ++ ) ans = (ans + dist[j] * i % mod * j % mod) % mod;
    }
    cout << ans;
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 98ms
memory: 17856kb

input:

200
20 160
90 160
5 90
78 90
186 90
149 90
104 78
136 160
106 78
100 106
168 90
30 5
85 136
28 149
1...

output:

104425891

result:

ok single line: '104425891'

Test #2:

score: 10
Accepted
time: 100ms
memory: 17860kb

input:

200
49 91
20 91
147 91
131 20
36 131
9 131
51 147
173 51
32 36
169 51
180 51
2 91
133 2
72 20
14 169...

output:

145567217

result:

ok single line: '145567217'

Test #3:

score: 10
Accepted
time: 97ms
memory: 17860kb

input:

200
44 72
187 72
115 72
124 115
80 124
34 72
22 115
162 34
123 44
93 22
135 80
5 124
112 72
76 187
3...

output:

226420652

result:

ok single line: '226420652'

Test #4:

score: 0
Time Limit Exceeded

input:

3000
940 1649
220 1649
1438 1649
2264 1649
1467 940
1825 220
1646 940
571 220
1419 220
2509 1438
264...

output:


result:


Test #5:

score: 0
Time Limit Exceeded

input:

3000
2156 216
2422 2156
2801 216
2504 2156
2701 2156
2582 2801
1558 2156
864 2582
737 864
2919 1558
...

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

3000
2966 2885
2657 2885
2613 2966
1686 2613
2803 2885
191 2657
2824 2657
675 2657
2693 191
2798 191...

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

1000000
984750 990109
970095 984750
996126 970095
998081 990109
987074 970095
962711 970095
916630 9...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

1000000
947305 936749
948062 947305
970449 947305
988744 948062
998703 988744
986194 947305
997762 9...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

1000000
952012 962256
982471 962256
955412 952012
953636 962256
991390 952012
998704 953636
999294 9...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

1000000
900864 972452
986047 900864
953966 972452
977801 986047
997024 972452
954755 953966
999240 9...

output:


result: