Submission details
Task:Osajono
Sender:kallam
Submission time:2015-10-12 02:28:18 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.05 s1details
#20.06 s1details
#30.06 s1details
#40.06 s1details
#50.05 s1details
#60.06 s2details
#70.06 s2details
#80.06 s2details
#90.06 s2details
#100.06 s2details
#110.06 s3details
#120.06 s3details
#130.06 s3details
#140.06 s3details
#150.07 s3details

Code

#include <iostream>
#include <list>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

bool mySort(pair<long long, int> a, pair<long long, int> b) {
  return a.first < b.first;
}

int main () {
  int n, m;
  int startnode, endnode, node;
  long long price;
  int midle;
  long long total;

  cin >> n;
  cin >> m;

  vector<pair<long long, int>> v[n+1];
  priority_queue<pair<long long,int>> q;

  bool t[n+1];
  long long e[n+1];

  for (int i = 0; i < m; ++i) {
    cin >> startnode >> endnode >> price;
    if(startnode == n) continue;
    v[endnode].push_back(make_pair(price, startnode));
  }

  for (int i = 1; i <= n; ++i) {
    e[i] = LLONG_MAX;
    t[i] = false;

  }

  //for (int i = 1; i < n; ++i) {
  //  sort(begin(v[i]), end(v[i]), mySort);
  //}

  e[n] = 0;
  q.push(make_pair(0,n));
  for (size_t i = 0; i < v[n].size(); ++i) {
    q.push(make_pair(-v[n][i].first, v[n][i].second));
  }

  while (!q.empty()) {
    price = -q.top().first;
    node = q.top().second;
    q.pop();
    if (t[node]) continue;
    if (node == 1) {
      cout << price << endl;
      return 0;
    }
    t[node] = true;
    for (size_t i = 0; i < v[node].size(); ++i) {
      total = price + v[node][i].first;
      if (total > e[1] - 2) continue;
      midle = v[node][i].second;
      for (size_t j = 0; j < v[midle].size() ; ++j) {
        endnode = v[midle][j].second;
        if ( total < e[endnode]) {
          e[endnode] = total;
          q.push(make_pair(-total, endnode));
        }
      }
    }
  }

  cout << "No route" << endl;

  return 1;
}

Test details

Test 1

Group: 1

Verdict:

input
BBBAABBBAAAABBAAAABAABAABBBBBB...

correct output
2554

user output
No route

Test 2

Group: 1

Verdict:

input
GDFVYWQCZAFGICSXOSWBZMGPDBSSVL...

correct output
299

user output
No route

Test 3

Group: 1

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAZAAAA...

correct output
4314

user output
No route

Test 4

Group: 1

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
4231

user output
No route

Test 5

Group: 1

Verdict:

input
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
5050

user output
No route

Test 6

Group: 2

Verdict:

input
BBABABBBABBAABBABBABAABAAABABA...

correct output
6253029

user output
No route

Test 7

Group: 2

Verdict:

input
RBKJMLDVQMKHYKCNDIVVKOMFUXTFMG...

correct output
485173

user output
No route

Test 8

Group: 2

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
12427725

user output
No route

Test 9

Group: 2

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
12467549

user output
No route

Test 10

Group: 2

Verdict:

input
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
12502500

user output
No route

Test 11

Group: 3

Verdict:

input
BAAAAABABBABAABAABABABBBABBAAB...

correct output
2500051369

user output
No route

Test 12

Group: 3

Verdict:

input
ABBURXDRVXAYBPXXOQZNYHLWGUEEWR...

correct output
192407124

user output
No route

Test 13

Group: 3

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
4998050400

user output
No route

Test 14

Group: 3

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
4998850144

user output
No route

Test 15

Group: 3

Verdict:

input
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
5000050000

user output
No route