| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 745881 |
2023-05-21T09:13:05 Z |
vjudge1 |
Cities (BOI16_cities) |
C++11 |
|
3392 ms |
66084 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int n,m,k;
vector<int> t[100005];
vector<int> w[100005];
vector<int> imp;
int a,b,c;
vector<int> dist[5];
void Dijkstra(int p,vector<int> &q) {
set<pair<int,int> > s; s.clear();
s.insert( {0,p} );
q.assign(n+1,-1);
int len,to;
while (s.size()>0) {
len=(*s.begin()).first;
to=(*s.begin()).second;
s.erase(s.begin());
if (q[to]==-1) {
q[to]=len;
for (int i=0;i<t[to].size();i++) {
s.insert( {len+w[to][i],t[to][i]} );
}
}
}
}
void kiir() {
for (int i=0;i<k;i++) {
cout << imp[i] << ": " << endl;
for (int j=1;j<=n;j++) {
cout << j << ": " << dist[i][j] << endl;
}
cout << endl;
}
}
vector<int> dis[1001];
void Dijkstra2(int p,vector<int> &q) {
set<pair<int,int> > s; s.clear();
s.insert( {0,p} );
q.assign(n+3,-1);
int len,to;
while (s.size()>0) {
len=(*s.begin()).first;
to=(*s.begin()).second;
s.erase(s.begin());
if (q[to]==-1) {
q[to]=len;
for (int i=0;i<t[to].size();i++) {
s.insert( {len+w[to][i],t[to][i]} );
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k >> m;
for (int i=1;i<=k;i++) {
cin >> a;
imp.push_back(a);
}
for (int i=1;i<=m;i++) {
cin >> a >> b >> c;
t[a].push_back(b);
t[b].push_back(a);
w[a].push_back(c);
w[b].push_back(c);
}
if (k==2) {
for (int i=0;i<k;i++) {
Dijkstra(imp[i],dist[i]);
}
cout << dist[0][imp[1]] << endl;
return(0);
}
if (k==3) {
for (int i=0;i<k;i++) {
Dijkstra(imp[i],dist[i]);
}
int ans=1e18;
for (int i=1;i<=n;i++) {
ans=min(ans,dist[0][i]+dist[1][i]+dist[2][i]);
}
cout << ans << endl;
return(0);
}
/*
if ((k==4) && (n<=1000)) {
for (int i=1;i<=n;i++) {
Dijkstra(i,dis[i]);
}
int ans=1e18;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
ans=min(ans,dis[imp[0]][i]+dis[imp[1]][i]+dis[i][j]+dis[j][imp[2]]+dis[j][imp[3]]);
ans=min(ans,dis[imp[0]][i]+dis[imp[2]][i]+dis[i][j]+dis[j][imp[1]]+dis[j][imp[3]]);
ans=min(ans,dis[imp[0]][i]+dis[imp[3]][i]+dis[i][j]+dis[j][imp[1]]+dis[j][imp[2]]);
}
}
cout << ans << endl;
return(0);
}
*/
if (k==4) {
int ans=1e18;
for (int i=0;i<k;i++) {
Dijkstra(imp[i],dist[i]);
}
vector<int> r;
for (int i=1;i<=n;i++) {
t[n+1].push_back(i);
w[n+1].push_back(dist[0][i]+dist[1][i]);
t[i].push_back(n+1);
w[i].push_back(dist[0][i]+dist[1][i]);
}
for (int i=1;i<=n;i++) {
t[n+2].push_back(i);
w[n+2].push_back(dist[2][i]+dist[3][i]);
t[i].push_back(n+2);
w[i].push_back(dist[2][i]+dist[3][i]);
}
Dijkstra2(n+1,r);
ans=min(ans,r[n+2]);
t[n+1].clear();
t[n+2].clear();
for (int i=1;i<=n;i++) {
t[i].pop_back();
t[i].pop_back();
}
for (int i=1;i<=n;i++) {
t[n+1].push_back(i);
w[n+1].push_back(dist[0][i]+dist[2][i]);
t[i].push_back(n+1);
w[i].push_back(dist[0][i]+dist[2][i]);
}
for (int i=1;i<=n;i++) {
t[n+2].push_back(i);
w[n+2].push_back(dist[1][i]+dist[3][i]);
t[i].push_back(n+2);
w[i].push_back(dist[1][i]+dist[3][i]);
}
Dijkstra2(n+1,r);
ans=min(ans,r[n+2]);
t[n+1].clear();
t[n+2].clear();
for (int i=1;i<=n;i++) {
t[i].pop_back();
t[i].pop_back();
}
for (int i=1;i<=n;i++) {
t[n+1].push_back(i);
w[n+1].push_back(dist[0][i]+dist[3][i]);
t[i].push_back(n+1);
w[i].push_back(dist[0][i]+dist[3][i]);
}
for (int i=1;i<=n;i++) {
t[n+2].push_back(i);
w[n+2].push_back(dist[2][i]+dist[1][i]);
t[i].push_back(n+2);
w[i].push_back(dist[2][i]+dist[1][i]);
}
Dijkstra2(n+1,r);
ans=min(ans,r[n+2]);
t[n+1].clear();
t[n+2].clear();
for (int i=1;i<=n;i++) {
t[i].pop_back();
t[i].pop_back();
}
cout << ans << endl;
return(0);
}
return 0;
}
Compilation message
cities.cpp: In function 'void Dijkstra(long long int, std::vector<long long int>&)':
cities.cpp:24:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i=0;i<t[to].size();i++) {
| ~^~~~~~~~~~~~~
cities.cpp: In function 'void Dijkstra2(long long int, std::vector<long long int>&)':
cities.cpp:53:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i=0;i<t[to].size();i++) {
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
988 ms |
29684 KB |
Output is correct |
| 2 |
Correct |
994 ms |
30440 KB |
Output is correct |
| 3 |
Correct |
186 ms |
13644 KB |
Output is correct |
| 4 |
Correct |
989 ms |
37868 KB |
Output is correct |
| 5 |
Correct |
808 ms |
28976 KB |
Output is correct |
| 6 |
Correct |
720 ms |
37708 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
5588 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
5564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3392 ms |
66084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
175 ms |
17340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
