oj.uz

Submission #380371

# Submission time Handle Problem Language Result Execution time Memory
380371 2021-03-21T07:39:11 Z loctildore Robot (JOI21_ho_t4) C++14
0 / 100
 599 ms 40096 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
int n,m;
int a,b,c,p;
struct edge{
  int target,c,p;
};
vector<edge> grph[100069];
set<int> grphcol[100069];
set<int> dupcol[100069];
bool done[100069];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>m;
  for (int i = 0; i < m; i++) {
    cin>>a>>b>>c>>p;
    a--;b--;
    grph[a].push_back({b,c,p});
    grph[b].push_back({a,c,p});
    if (grphcol[a].find(c)!=grphcol[a].end()) {
      if (dupcol[a].find(c)==dupcol[a].end()) {
        dupcol[a].insert(c);
      }
    }
    else{
      grphcol[a].insert(c);
    }
    if (grphcol[b].find(c)!=grphcol[b].end()) {
      if (dupcol[b].find(c)==dupcol[b].end()) {
        dupcol[b].insert(c);
      }
    }
    else{
      grphcol[b].insert(c);
    }
  }
  pq.push({0,0});
  while (pq.size()) {
    auto temp=pq.top();
    pq.pop();
    if (done[temp.s]) {
      continue;
    }
    done[temp.s]=true;
    if (temp.s==n-1) {
      cout<<temp.f<<endl;
      return 0;
    }
    for (auto i:grph[temp.s]) {
      if (dupcol[temp.s].find(i.c)==dupcol[temp.s].end()) {
        pq.push({temp.f,i.target});
      }
      else{
        pq.push({temp.f+i.p,i.target});
      }
    }
  }
  cout<<"-1"<<endl;
  return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12268 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 8 ms 12140 KB Output is correct
7 Incorrect 9 ms 12268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 22376 KB Output is correct
2 Correct 54 ms 17132 KB Output is correct
3 Correct 131 ms 22508 KB Output is correct
4 Correct 74 ms 18740 KB Output is correct
5 Incorrect 599 ms 40096 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12268 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 8 ms 12140 KB Output is correct
7 Incorrect 9 ms 12268 KB Output isn't correct
8 Halted 0 ms 0 KB -