Tickets for Connected Transit Lines
National Olympiad — National round
Submission name: travelling.cpp
Problem summary
A connected undirected multigraph has N stops and M streets. Each street belongs to exactly one of K transport lines, and the streets of each line form a connected subgraph. A line is a trolleybus or tram and has a positive price; its ticket covers all uses of that line for the day. Travel from stop 1 to stop N with minimum total ticket cost; among cheapest choices, minimize the number of distinct tram lines used.
Input
N M K; K types (0 trolleybus, 1 tram); K prices; then M triples u v t.
Output
Minimum cost and, second, minimum tram-line count among minimum-cost journeys.
Constraints
2 ≤ N ≤ 100,000; N ≤ M ≤ 1,000,000; 1 ≤ K ≤ M; 1 ≤ price ≤ 10⁹; endpoints distinct; parallel streets allowed.
Worked example
An independently prepared example for this explanation.
Input
3 3 3 1 0 0 2 1 1 1 3 1 1 2 2 2 3 3
Output
2 0
Solution analysis
- Create one additional node per line. From each incident stop, entering its line costs (price,type); returning from a line node to any incident stop costs (0,0).
- Run Dijkstra with lexicographically ordered pairs (money,tram count). A line is connected, so its internal street layout can be replaced by this hub.
Why it works
Any selected ticket permits reaching all stops of its connected line. An optimal hub path need not visit a line node twice: remove the intervening cycle, which cannot improve either nonnegative criterion. Thus charging once per entry yields the optimum even though tickets are reusable. Dijkstra applies to lexicographic nonnegative weights.
Watch out. Charging each street separately is wrong. Monetary sums need 64 bits; compare money before tram count.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Any selected ticket permits reaching all stops of its connected line. An optimal hub path
// need not visit a line node twice: remove the intervening cycle, which cannot improve either
// nonnegative criterion.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>
#include<tuple>
#include<climits>
#include<functional>
using namespace std;
using ll=long long;
using P=pair<ll,int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,k;
cin>>n>>m>>k;
vector<int>type(k);
vector<ll>cost(k);
for(int&x:type){
cin>>x;
}
for(ll&x:cost){
cin>>x;
}
vector<vector<int>>g(n+k);
for(int i=0;i<m;i++){
int u,v,t;
cin>>u>>v>>t;
--u;
--v;
--t;
g[u].push_back(n+t);
g[v].push_back(n+t);
g[n+t].push_back(u);
g[n+t].push_back(v);
}
vector<P>d(n+k,{LLONG_MAX,INT_MAX});
priority_queue<pair<P,int>,vector<pair<P,int>>,greater<pair<P,int>>>pq;
d[0]={0,0};
pq.push({d[0],0});
while(!pq.empty()){
auto[du,u]=pq.top();
pq.pop();
if(du!=d[u]){
continue;
}
for(int v:g[u]){
P nd=du;
if(v>=n){
nd.first+=cost[v-n];
nd.second+=type[v-n];
}
if(nd<d[v]){
d[v]=nd;
pq.push({nd,v});
}
}
}
cout<<d[n-1].first<<' '<<d[n-1].second<<'\n';
}