#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 500005;
int ka()
{
int x = 0;
while (1)
{
char y = getchar();
if ('0' <= y && y <= '9')
x = (x * 10) + (y - '0');
else
return x;
}
}
struct ban
{
int x, d;
ban(){}
ban(int x, int d)
{
this->x = x;
this->d = d;
}
};
bool operator<(const ban& a, const ban& b)
{
return a.d < b.d;
}
int n, m;
vector<ban> a[N];
bool c[N];
int ans[N];
vector<ban> q[N];
void prr()
{
int j = N - 1;
q[N - 1].push_back(ban(1, N - 1));
while (1)
{
ban t;
do
{
if (j == -1)
return;
if (q[j].empty())
{
--j;
continue;
}
t = q[j].back();
q[j].pop_back();
} while (c[t.x]);
c[t.x] = true;
ans[t.x] = t.d;
for (int i = 0; i < a[t.x].size(); ++i)
{
ban h = a[t.x][i];
h.d = min(h.d, t.d);
if (!c[h.x])
q[h.d].push_back(h);
}
}
}
void solv()
{
int qq;
n = ka();
m = ka();
qq = ka();
for (int i = 0; i < m; ++i)
{
int x, y, z;
x = ka();
y = ka();
z = ka();
a[x].push_back(ban(y, z));
a[y].push_back(ban(x, z));
}
prr();
while (qq--)
{
int x;
x = ka();
printf("%d\n", ans[x]);
}
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
//ios_base::sync_with_stdio(false), cin.tie(0);
solv();
return 0;
}
//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}
Compilation message
sightseeing.cpp: In function 'void prr()':
sightseeing.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[t.x].size(); ++i)
~~^~~~~~~~~~~~~~~
sightseeing.cpp:55:13: warning: 't.ban::d' may be used uninitialized in this function [-Wmaybe-uninitialized]
ban t;
^
sightseeing.cpp:67:23: warning: 't.ban::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
} while (c[t.x]);
~~~~~^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23808 KB |
Output is correct |
2 |
Correct |
20 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
24064 KB |
Output is correct |
2 |
Correct |
21 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
27000 KB |
Output is correct |
2 |
Correct |
42 ms |
26364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2918 ms |
147048 KB |
Output is correct |
2 |
Execution timed out |
3593 ms |
183500 KB |
Time limit exceeded |