#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf 1000000000
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
int n, m, k, Q;
vii ke[maxn];
int d[maxn], arr[maxn];
bool ok[maxn];
namespace sub2
{
int f[N][N];
priority_queue<pii, vii, greater<pii>> q;
void dijkstra()
{
while (q.size())
{
auto [du, u] = q.top();
q.pop();
if (du != d[u])
continue;
for (auto [v, w] : ke[u])
{
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
}
struct node
{
int du, u;
};
bool operator<(node a, node b)
{
return a.du > b.du;
}
void dij(int i)
{
fo(j, 1, n) f[i][j] = -1;
priority_queue<node> q;
q.push({f[i][i], i});
while (q.size())
{
auto [du, u] = q.top();
q.pop();
if (f[i][u] != du)
continue;
for (auto [v, w] : ke[u])
{
int val;
if(f[i][u] == -1) val = d[v];
else val = min(f[i][u],d[v]);
if (f[i][v] < val)
{
f[i][v] = val;
q.push({d[v], v});
}
}
}
}
void solve()
{
fo(i, 1, n) d[i] = inf;
fo(i, 1, k) q.push({0, arr[i]}), d[arr[i]] = 0;
dijkstra();
fo(i, 1, n)
{
dij(i);
}
while (Q--)
{
int u, v;
cin >> u >> v;
if(d[u] == 0 or d[v] == 0) cout << 0 << "\n";
else
cout << f[u][v] << "\n";
}
}
}
namespace sub3
{
priority_queue<pii, vii, greater<pii>> q;
int f[maxn];
void dijkstra()
{
while (q.size())
{
auto [du, u] = q.top();
q.pop();
if (du != d[u])
continue;
for (auto [v, w] : ke[u])
{
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
}
struct node
{
int du, u;
};
bool operator<(node a, node b)
{
return a.du > b.du;
}
void dij(int i)
{
fo(j, 1, n) f[j] = -1;
priority_queue<node> q;
q.push({f[i], i});
while (q.size())
{
auto [du, u] = q.top();
q.pop();
if (f[u] != du)
continue;
for (auto [v, w] : ke[u])
{
int val;
if(f[u] == -1) val = d[v];
else val = min(f[u],d[v]);
if (f[v] < val)
{
f[v] = val;
q.push({d[v], v});
}
}
}
}
void solve()
{
fo(i, 1, n) d[i] = inf;
fo(i, 1, k) q.push({0, arr[i]}), d[arr[i]] = 0;
dijkstra();
int u, v;
cin >> u >> v;
fo(i, 1, n) f[i] = inf;
dij(u);
if(d[u] == 0 or d[v] == 0) cout << 0;
else
cout << f[v];
}
}
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
fo(i, 1, m)
{
int u, v, w;
cin >> u >> v >> w;
ke[u].pb(v, w);
ke[v].pb(u, w);
}
cin >> k;
fo(i, 1, k) cin >> arr[i];
cin >> Q;
if (m <= 200)
sub2::solve();
if (Q == 1)
sub3::solve();
}
Compilation message
plan.cpp:185:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
185 | main()
| ^~~~
plan.cpp: In function 'int main()':
plan.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
190 | freopen(name ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
191 | freopen(name ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
31580 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
31580 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
31736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
115 ms |
50832 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
31580 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |