Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long int lli;
- typedef pair<int,int> pii;
- int main(){
- int n,m,t,x,y;
- scanf("%d %d %d",&n,&m,&t);
- vector<pii> adj[n+3];
- scanf("%d %d",&x,&y);
- for(int i=0;i<m;++i){
- int u,v,w;
- scanf("%d %d %d",&u,&v,&w);
- adj[u].push_back({v,w});
- }
- priority_queue<pair<lli,pii>,vector<pair<lli,pii>>,greater<pair<lli,pii>>> pq;
- pq.push({0,{x,1}});
- vector<vector<bool>> visited(n+3,vector<bool>(t+1,false));
- while(!pq.empty()){
- lli d = pq.top().first;
- int u = pq.top().second.first;
- int k = pq.top().second.second;
- pq.pop();
- if(k == 0 && u == y){
- printf("%lld",d);
- return 0;
- }
- if(visited[u][k]){
- continue;
- }
- visited[u][k] = true;
- for(auto v : adj[u]){
- if(!visited[v.first][(k+1)%t]){
- pq.push({d + v.second,{v.first,(k+1)%t}});
- }
- }
- }
- printf("-1");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement