QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56962 | #3893. Family Fares | MahmoudAtia | WA | 3ms | 3772kb | C++ | 2.2kb | 2022-10-22 07:23:20 | 2022-10-22 07:23:22 |
Judging History
answer
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, -1, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 1, 1, -1};
const ll oo = 1e18, MOD = 998244353;
const int N = 1005, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n, m, p, g, idx[N], dis[N][N], vis[N][N];
vector<pair<int, int> > v[N];
void dijkstra(int s) {
for (int i = 1; i <= n; i++) dis[s][i] = 2e9;
dis[s][s] = 0;
priority_queue<pair<int, int>> q;
q.push({0, s});
while (!q.empty()) {
int node = q.top().second, cost = -q.top().first;
q.pop();
if (cost != dis[s][node]) continue;
for (auto x:v[node]) {
if (dis[s][x.first] > x.second + dis[s][node]) {
dis[s][x.first] = x.second + dis[s][node];
q.push({-dis[s][x.first], x.first});
}
}
}
}
void build(int s, int node) {
cout << s << " " << node << endl;
vis[s][node] = 1;
for (auto x:v[node]) {
if (dis[1][node] == dis[1][x.first] + x.second && !vis[s][x.first]) {
build(s, x.first);
}
}
}
//#define endl '\n'
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("farm.in", "r", stdin);
//memset(dp, -1, sizeof dp);
cin >> n >> m >> p >> g;
for (int i = 1; i <= p; i++) cin >> idx[i];
while (m--) {
int x, y, c;
cin >> x >> y >> c;
v[x].push_back({y, c});
v[y].push_back({x, c});
}
dijkstra(1);
for (int i = 1; i <= p; i++) dijkstra(idx[i]);
for (int i = 1; i <= p; i++) build(idx[i], idx[i]);
int ans = 2e9;
for (int i = 1; i <= n; i++) {
int tmp = 0;
for (int j = 1; j <= p; j++) {
if (vis[idx[j]][i]) tmp += min(dis[idx[j]][1], g + dis[idx[j]][i]);
else tmp += dis[idx[j]][1];
}
ans = min(ans, tmp);
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 3772kb
input:
6 5 3 10 4 5 6 1 2 10 2 3 10 3 4 10 4 5 2 4 6 3
output:
4 4 4 3 4 2 4 1 5 5 5 4 5 3 5 2 5 1 6 6 6 4 6 3 6 2 6 1 35
result:
wrong answer 1st lines differ - expected: '35', found: '4 4'