// #pragma GCC optimize("O3")
#include <cstdio>
#include <queue>
using namespace std;
int main(){
int n, k, m;
scanf("%d%d%d", &n, &k, &m);
vector <vector <int> > adjLis1(n);
vector <vector <long long> > disLis1(n);
vector <int> important(k);
for(int& i:important){
scanf("%d", &i);
i--;
}
while(k<5){
important.push_back(important.back());
k++;
}
for(int i = m;i --;){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--;b--;
adjLis1[a].push_back(b);
disLis1[a].push_back(c);
adjLis1[b].push_back(a);
disLis1[b].push_back(c);
}
vector <vector <long long> > multisource(k, vector <long long> (n, 1e14));
for(int i = 0;i < k;i ++){
vector <long long>& dist=multisource[i];
int source=important[i];
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis1[x].size();i ++){
int y=adjLis1[x][i];
long long dd=disLis1[x][i];
if(dist[y]>d+dd){
dist[y]=d+dd;
dijkstra.push(make_pair(dist[y], y));
}
}
}
}
if(k==5){
vector <vector <long long> > two;
int x, y;
//0 1
x=0, y=1;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//0 2
x=0, y=2;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//0 3
x=0, y=3;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//0 4
x=0, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//1 2
x=1, y=2;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//1 3
x=1, y=3;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//1 4
x=1, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//2 3
x=2, y=3;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//2 4
x=2, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
//3 4
x=3, y=4;
{
vector <vector <int> > adjLis2=adjLis1;
vector <vector <long long> > disLis2=disLis1;
adjLis2.resize(n+1);
disLis2.resize(n+1);
for(int i = 0;i < n;i ++){
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[x][i]+multisource[y][i]);
}
int source=n;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
two.push_back(vector <long long> (n+1, 1e14));
vector <long long>& dist=two.back();
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=d+disLis2[x][i];
if(dist[y]>dd){
dist[y]=dd;
dijkstra.push(make_pair(dd, y));
}
}
}
dist.pop_back();
}
long long best=1e14;
for(int i = 0;i < n;i ++){
best=min(best, two[0][i]+two[7][i]+multisource[4][i]);
best=min(best, two[1][i]+two[5][i]+multisource[4][i]);
best=min(best, two[2][i]+two[4][i]+multisource[4][i]);
best=min(best, two[0][i]+two[8][i]+multisource[3][i]);
best=min(best, two[1][i]+two[6][i]+multisource[3][i]);
best=min(best, two[3][i]+two[4][i]+multisource[3][i]);
best=min(best, two[0][i]+two[9][i]+multisource[2][i]);
best=min(best, two[2][i]+two[6][i]+multisource[2][i]);
best=min(best, two[3][i]+two[5][i]+multisource[2][i]);
best=min(best, two[1][i]+two[9][i]+multisource[1][i]);
best=min(best, two[2][i]+two[8][i]+multisource[1][i]);
best=min(best, two[3][i]+two[7][i]+multisource[1][i]);
best=min(best, two[4][i]+two[9][i]+multisource[0][i]);
best=min(best, two[5][i]+two[8][i]+multisource[0][i]);
best=min(best, two[6][i]+two[7][i]+multisource[0][i]);
}
printf("%lld\n", best);
}
}
Compilation message
cities.cpp: In function 'int main()':
cities.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis1[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:146:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:180:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:214:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:248:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:282:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:316:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:350:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:384:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adjLis2[x].size();i ++){
~~^~~~~~~~~~~~~~~~~~~
cities.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &k, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &i);
~~~~~^~~~~~~~~~
cities.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
0 ms |
256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1605 ms |
47836 KB |
Output is correct |
| 2 |
Correct |
1597 ms |
48540 KB |
Output is correct |
| 3 |
Correct |
1127 ms |
39864 KB |
Output is correct |
| 4 |
Correct |
137 ms |
11596 KB |
Output is correct |
| 5 |
Correct |
1554 ms |
47872 KB |
Output is correct |
| 6 |
Correct |
138 ms |
11592 KB |
Output is correct |
| 7 |
Correct |
9 ms |
836 KB |
Output is correct |
| 8 |
Correct |
7 ms |
840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
852 KB |
Output is correct |
| 2 |
Correct |
7 ms |
860 KB |
Output is correct |
| 3 |
Correct |
5 ms |
752 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1575 ms |
47784 KB |
Output is correct |
| 2 |
Correct |
1510 ms |
48456 KB |
Output is correct |
| 3 |
Correct |
1115 ms |
39640 KB |
Output is correct |
| 4 |
Correct |
1031 ms |
30284 KB |
Output is correct |
| 5 |
Correct |
308 ms |
15316 KB |
Output is correct |
| 6 |
Correct |
158 ms |
13924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1624 ms |
47852 KB |
Output is correct |
| 2 |
Correct |
1927 ms |
47800 KB |
Output is correct |
| 3 |
Correct |
1499 ms |
48328 KB |
Output is correct |
| 4 |
Correct |
1244 ms |
39956 KB |
Output is correct |
| 5 |
Correct |
1012 ms |
29420 KB |
Output is correct |
| 6 |
Correct |
280 ms |
15372 KB |
Output is correct |
| 7 |
Correct |
153 ms |
13936 KB |
Output is correct |
