Investigation

tepyotin2

Jun 10th, 2025

629

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.56 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long V = 1e18;
const long long MOD = 1e9+7;
struct Edge{
int to;
ll val;
};
struct Node{
int node;
ll weight;
//ll count;
bool operator>(const Node &a) const{
return weight>a.weight;
}
};
int n, m;
vector<vector<Edge>> con;
priority_queue<Node, vector<Node>, greater<Node>> pq;
vector<ll> dist;
//vector<vector<ll>> sizes;
//ll mod = 1e9+7;
//ll mn_flight[100001];
//ll mx_flight[100001];
//ll way[100001];
//ll v = 1e18;
int main(){
//freopen("investigation.in", "r", stdin);
cin >> n >> m;
con.resize(n+1);
dist.resize(n+1, V);
//sizes.resize(n+1);
//memset(mn_flight, v, sizeof(mn_flight));
vector<int> mn_flight(n+1, INT_MAX);
vector<int> mx_flight(n+1, 0);
vector<ll> way(n+1, 0);
for(int i=0; i<m; i++){
int a, b;
ll c;
cin >> a >> b >> c;
con[a].push_back({b, c});
}
pq.push({1, 0});
dist[1] = 0;
way[1] = 1;
mn_flight[1] = 0;
while(!pq.empty()){
Node cur = pq.top();
pq.pop();
int node = cur.node;
ll weight = cur.weight;
if(weight>dist[node]) continue;
//cout << "node: " << node << ", weight: " << weight << ", dist: " << dist[node] << ", way: " << way[node] << '\n';
//way[node]++;
//way[node] = way[node]%MOD;
//sizes[node].push_back(cur.count);
for(Edge v: con[node]){
if(dist[v.to]>dist[node]+v.val){
dist[v.to] = dist[node]+v.val;
pq.push({v.to, dist[v.to]});
way[v.to] = way[node];
//cout << "1: " << "node: " << node << ", to: " << v.to << ", dist[node]: " << dist[node] << ", way[v.to]: " << way[v.to] << '\n';
//way[v.to]++;
mn_flight[v.to] = mn_flight[node]+1;
mx_flight[v.to] = mx_flight[node]+1;
}else if(dist[v.to] == dist[node]+v.val){
//sizes[v.to].push_back(cur.count+1);
//pq.push({v.to, dist[v.to]});
//!!!Must not push same values into priority queue because way values
//will be doubled for absolutely no reason at all
//cout << "2: " << "node: " << node << ", to: " << v.to << ", way[node]: " << way[node] << ", way[v.to]: " << way[v.to] << '\n';
//cout << "dist[v.to]: " << dist[v.to] << ", " << "dist[node]+v.val: " << dist[node]+v.val << '\n';
way[v.to] = (way[node]+way[v.to])%MOD;
mn_flight[v.to] = min(mn_flight[v.to], mn_flight[node]+1);
mx_flight[v.to] = max(mx_flight[v.to], mx_flight[node]+1);
}
}
}
cout << dist[n] << " ";
cout << way[n] << " ";
//sort(sizes[n].begin(), sizes[n].end());
cout << mn_flight[n] << " ";
cout << mx_flight[n] << '\n';
return 0;
}

Add Comment

Please, Sign In to add comment