Ping

input/code.cpp: In function 'int dijkstra(const std::vector<Vertex>&, int)':
input/code.cpp:56:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < neighbours.size(); ++i) {
                           ^

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <set>
#include <queue>
#include <tuple>
 
typedef long long LL;
 
using namespace std;
 
LL nVertices, nUpdates, target;
 
struct Edge {
    int target;
    int weight;
};
struct Vertex {
    vector<Edge> neighbours;
};
struct FVertex {
    LL f;
    int target;
};
 
vector<tuple<int,int,int> > updates;
//vector<Vertex> vertices;
 
int dijkstra(const vector<Vertex>& network, int startnode)
{
    auto comp = [](FVertex f1, FVertex f2){ return f1.f > f2.f; };
    priority_queue<FVertex, vector<FVertex>, decltype(comp)> q(comp);
    
    set<int> visited;
    q.push({0, startnode});
    
    while (!q.empty())  {
        FVertex f = q.top(); q.pop();
        
        if (visited.find(f.target) != visited.end())
            continue;
        
        visited.insert(f.target);
        //cout << "The shortest path to " << f.target << " is " << f.f << " units long" << endl;
        
        if(f.target == nVertices-1){
            //cout << "Distance: " << f.f << endl;
            if(f.f <= target) return true;
            return false;
        }
        
        const vector<Edge>& neighbours = network[f.target].neighbours;
        for (int i = 0; i < neighbours.size(); ++i) {
            FVertex nextf;
            nextf.f = f.f + neighbours[i].weight;
            nextf.target = neighbours[i].target;
            q.push(nextf);
        }
    }
    return false; // Not connected
};
 
bool check(LL time){
    if(time < 0) return false;
    vector<Vertex> graph(nVertices);
    for(int i = 0; i < time; i++){
        int from = get<0>(updates[i]);
        int to = get<1>(updates[i]);
        int dist = get<2>(updates[i]);
        graph[from].neighbours.push_back({to, dist});
        graph[to].neighbours.push_back({from, dist});
    }
    bool result = dijkstra(graph,0);
    return result;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> nVertices >> nUpdates >> target;
    for(int i = 0; i < nUpdates; i++){
        int u,v,d;
        cin >> u >> v >> d;
        updates.push_back(make_tuple(u-1,v-1,d));
    }
    LL time = nUpdates+1;
    LL step = (1LL) << 30;
    while(step != 0){
        if(check(time-step)){
            time -= step;
        }
        step /= 2;
    }
    
    if(time == nUpdates + 1) cout << "QAQ" << endl;
    else cout <<  time << endl;
}
 
 
 
 

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED