| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 745952 |
2023-05-21T09:59:30 Z |
vjudge1 |
Cities (BOI16_cities) |
C++11 |
|
6000 ms |
53168 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n,m,k;
vector<int> t[100005];
vector<ll> w[100005];
vector<int> imp;
int a,b,c;
vector<ll> dist[5];
void Dijkstra(int p,vector<ll> &q) {
set<pair<ll,int> > s; s.clear();
s.insert( {ll(0),p} );
q.assign(n+1,-1);
ll len;
int 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<ll> dis[1001];
void Dijkstra2(int p,vector<ll> &q) {
set<pair<ll,int> > s; s.clear();
s.insert( {0,p} );
q.assign(n+3,-1);
ll len;
int 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]} );
}
}
}
}
int 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]);
}
ll 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]);
}
ll 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) {
ll ans=1e18;
for (int i=0;i<k;i++) {
Dijkstra(imp[i],dist[i]);
}
//kiir();
vector<ll> 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]);
for (int i=1;i<=n;i++) {
w[i].pop_back();
w[i].pop_back();
w[n+1][i-1]=dist[0][i]+dist[2][i];
w[i].push_back(dist[0][i]+dist[2][i]);
}
for (int i=1;i<=n;i++) {
w[n+2][i-1]=dist[1][i]+dist[3][i];
w[i].push_back(dist[1][i]+dist[3][i]);
}
Dijkstra2(n+1,r);
ans=min(ans,r[n+2]);
for (int i=1;i<=n;i++) {
w[i].pop_back();
w[i].pop_back();
w[n+1][i-1]=dist[0][i]+dist[3][i];
w[i].push_back(dist[0][i]+dist[3][i]);
}
for (int i=1;i<=n;i++) {
w[n+2][i-1]=dist[2][i]+dist[1][i];
w[i].push_back(dist[2][i]+dist[1][i]);
}
Dijkstra2(n+1,r);
ans=min(ans,r[n+2]);
cout << ans << endl;
return(0);
}
if (k==5) {
for (int i=1;i<=n;i++) {
Dijkstra(i,dis[i]);
}
ll ans=1e18;
vector<int> a; a=imp;
for (int i=0;i<120;i++) {
for (int i=1;i<n;i++) {
for (int j=1;j<=n;j++) {
for (int l=1;l<=n;l++) {
ans=min(ans,dis[a[0]][i]+dis[a[1]][i]+dis[a[2]][j]+dis[a[3]][j]+dis[a[4]][k]+dis[i][k]+dis[j][k]);
}
}
}
next_permutation(a.begin(),a.end());
}
cout << ans << endl;
}
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(int, std::vector<long long int>&)':
cities.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i=0;i<t[to].size();i++) {
| ~^~~~~~~~~~~~~
cities.cpp: In function 'void Dijkstra2(int, std::vector<long long int>&)':
cities.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i=0;i<t[to].size();i++) {
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 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 |
5 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
4948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1008 ms |
28012 KB |
Output is correct |
| 2 |
Correct |
1008 ms |
28528 KB |
Output is correct |
| 3 |
Correct |
170 ms |
13640 KB |
Output is correct |
| 4 |
Correct |
1000 ms |
35744 KB |
Output is correct |
| 5 |
Correct |
728 ms |
27260 KB |
Output is correct |
| 6 |
Correct |
749 ms |
35740 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
806 ms |
13020 KB |
Output is correct |
| 2 |
Correct |
768 ms |
12976 KB |
Output is correct |
| 3 |
Correct |
222 ms |
12844 KB |
Output is correct |
| 4 |
Correct |
429 ms |
7228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3450 ms |
50236 KB |
Output is correct |
| 2 |
Correct |
2950 ms |
53168 KB |
Output is correct |
| 3 |
Correct |
1081 ms |
41076 KB |
Output is correct |
| 4 |
Correct |
2933 ms |
41772 KB |
Output is correct |
| 5 |
Correct |
2561 ms |
35992 KB |
Output is correct |
| 6 |
Execution timed out |
6021 ms |
38428 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6007 ms |
43588 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
