| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 745923 |
2023-05-21T09:41:44 Z |
vjudge1 |
Cities (BOI16_cities) |
C++11 |
|
2114 ms |
109740 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]);
}
//kiir();
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]);
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]);
for (int i=1;i<=n;i++) {
w[n+1][i]=dist[0][i]+dist[2][i];
w[i][n+1]=dist[0][i]+dist[2][i];
}
for (int i=1;i<=n;i++) {
w[n+2][i]=dist[1][i]+dist[3][i];
w[i][n+2]=dist[1][i]+dist[3][i];
}
Dijkstra2(n+1,r);
ans=min(ans,r[n+2]);
for (int i=1;i<=n;i++) {
w[n+1][i]=dist[0][i]+dist[3][i];
w[i][n+1]=dist[0][i]+dist[3][i];
}
for (int i=1;i<=n;i++) {
w[n+2][i]=dist[2][i]+dist[1][i];
w[i][n+2]=dist[2][i]+dist[1][i];
}
Dijkstra2(n+1,r);
ans=min(ans,r[n+2]);
cout << ans << endl;
return(0);
}
return 0;
}
/*
8 4 12
1 3 4 7
1 2 1
2 3 1
3 4 20
4 5 6
5 6 9
6 7 11
7 8 10
1 8 4
8 4 5
2 7 8
3 6 3
5 7 6
*/
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 |
1014 ms |
29728 KB |
Output is correct |
| 2 |
Correct |
968 ms |
30276 KB |
Output is correct |
| 3 |
Correct |
198 ms |
13644 KB |
Output is correct |
| 4 |
Correct |
987 ms |
37916 KB |
Output is correct |
| 5 |
Correct |
702 ms |
28980 KB |
Output is correct |
| 6 |
Correct |
704 ms |
37748 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
752 ms |
12980 KB |
Output is correct |
| 2 |
Correct |
888 ms |
13064 KB |
Output is correct |
| 3 |
Correct |
205 ms |
12904 KB |
Output is correct |
| 4 |
Correct |
414 ms |
7220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2114 ms |
109740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
17356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
