oj.uz

Submission #951246

# Submission time Handle Problem Language Result Execution time Memory
951246 2024-03-21T13:32:09 Z NourWael Relay Marathon (NOI20_relaymarathon) C++17
5 / 100
 6000 ms 4952 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 1e3+5;
vector<pair<int,int>> adj[mxN];
vector<int> spe;
bool is[mxN], vis[mxN];
int dist[mxN][mxN], cur[mxN];
int n; 

void solve ( int i , int e1, int e2, bool f) {

   memset(vis,0,sizeof vis);
   for(int j=1; j<=n; j++) cur[j] = 1e18;
   priority_queue<pair<int,int>> q;
   q.push({0,i});
   
   while(q.size()) {
     int node = q.top().second, d = -(q.top().first);
     q.pop();
     if(vis[node]) continue;
     vis[node] = 1;
     for(auto it:adj[node]) {
      if(cur[it.first]<=d+it.second) continue;
      cur[it.first] = d+it.second;
      q.push({-(d+it.second), it.first});
     }
   }

   for(int j=1; j<=n; j++) dist[i][j] = cur[j];
}
signed main() {
  
  ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
 
   int m,k; cin>>n>>m>>k;
   for(int i=0; i<m; i++) {
      int x,y,c; cin>>x>>y>>c;
      adj[x].push_back({y,c}), adj[y].push_back({x,c});
   }
   
   for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j] = 1e18; 
   for(int i=0; i<k; i++) {
      int x; cin>>x;
      is[x] = 1;
      spe.push_back(x);
   }
   
   for(int i=1; i<=n; i++) solve(i, 0, 0, 0);
    
   int ans = 1e18;

   for(int i=1; i<=n; i++) {
      if(!is[i]) continue;
      for(int j=1; j<=n; j++) {
         if(!is[j] || j==i) continue;
         for(int h=1; h<=n; h++) {
            if(!is[h] || h==i || h==j) continue;
            for(int l=1; l<=n; l++) {
              if(!is[l] || l==i || l==j || l==h) continue;
              if(dist[i][j] + dist[h][l]<ans) { ans = dist[i][j] + dist[h][l];}
            }
         }
      }
   }

   cout<<ans;
   return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2540 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 4 ms 2724 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 9 ms 2636 KB Output is correct
12 Correct 6 ms 2648 KB Output is correct
13 Correct 10 ms 2652 KB Output is correct
14 Correct 3 ms 2652 KB Output is correct
15 Correct 12 ms 2724 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 12 ms 2652 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 12 ms 2724 KB Output is correct
20 Correct 3 ms 2652 KB Output is correct
21 Correct 7 ms 2652 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 10 ms 2680 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 2 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 10 ms 2652 KB Output is correct
29 Correct 3 ms 2652 KB Output is correct
30 Correct 4 ms 2652 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2540 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 4 ms 2724 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 9 ms 2636 KB Output is correct
12 Correct 6 ms 2648 KB Output is correct
13 Correct 10 ms 2652 KB Output is correct
14 Correct 3 ms 2652 KB Output is correct
15 Correct 12 ms 2724 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 12 ms 2652 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 12 ms 2724 KB Output is correct
20 Correct 3 ms 2652 KB Output is correct
21 Correct 7 ms 2652 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 10 ms 2680 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 2 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 10 ms 2652 KB Output is correct
29 Correct 3 ms 2652 KB Output is correct
30 Correct 4 ms 2652 KB Output is correct
31 Correct 7 ms 4700 KB Output is correct
32 Correct 20 ms 4952 KB Output is correct
33 Correct 23 ms 4812 KB Output is correct
34 Correct 3 ms 4700 KB Output is correct
35 Correct 2 ms 4700 KB Output is correct
36 Execution timed out 6060 ms 4852 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2540 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 4 ms 2724 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 9 ms 2636 KB Output is correct
12 Correct 6 ms 2648 KB Output is correct
13 Correct 10 ms 2652 KB Output is correct
14 Correct 3 ms 2652 KB Output is correct
15 Correct 12 ms 2724 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 12 ms 2652 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 12 ms 2724 KB Output is correct
20 Correct 3 ms 2652 KB Output is correct
21 Correct 7 ms 2652 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 10 ms 2680 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 2 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 10 ms 2652 KB Output is correct
29 Correct 3 ms 2652 KB Output is correct
30 Correct 4 ms 2652 KB Output is correct
31 Correct 7 ms 4700 KB Output is correct
32 Correct 20 ms 4952 KB Output is correct
33 Correct 23 ms 4812 KB Output is correct
34 Correct 3 ms 4700 KB Output is correct
35 Correct 2 ms 4700 KB Output is correct
36 Execution timed out 6060 ms 4852 KB Time limit exceeded
37 Halted 0 ms 0 KB -