fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int64_t inf = 1e18;
  5. const int N = 5005;
  6.  
  7. struct Dijkstra{
  8.     int u;
  9.     int64_t d;
  10.     bool operator < (const Dijkstra &oth) const{
  11.         return oth.d>d;
  12.     }
  13. };
  14.  
  15. int64_t dist[N], dp[N];
  16.  
  17. int main(){
  18.     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  19.     int n, m; cin >> n >> m;
  20.     vector<vector<pair<int, int64_t> > > adj(n + 1);
  21.     for(int i=0; i<m; i++){
  22.         int t, u, v, l;
  23.         cin >> t >> u >> v >> l;
  24.         adj[u].push_back({v, l});
  25.         if (t==2) adj[v].push_back({u, l});
  26.     }
  27.     //khoi tao
  28.     for(int i=1; i<=n; i++){
  29.         dp[i] = 0;
  30.         dist[i] = inf;
  31.     }
  32.     dp[1] = 1; dist[1] = 0; 
  33.     //dijkstra
  34.     priority_queue<Dijkstra> pq;
  35.     pq.push({1, 0});
  36.     while (pq.size()){
  37.         int u = pq.top().u;
  38.         int cur = pq.top().d;
  39.         pq.pop();
  40.         for(int i=0; i<adj[u].size(); i++){
  41.             int v = adj[u][i].first;
  42.             int64_t w = adj[u][i].second;
  43.             if (dist[v] > dist[u] + w){
  44.                 dist[v] = dist[u] + w;
  45.                 dp[v] = dp[u];
  46.                 pq.push({v, dist[v]});
  47.             }
  48.             else if (dist[v]==dist[u] + w){
  49.                 //tong so duong di ngan nhat tu 1 den v cong voi tong so duong di ngan nhat tu 1 den u
  50.                 dp[v] += dp[u];
  51.             }
  52.         }
  53.     }
  54.     cout << dist[n] << " " << dp[n];
  55.     return 0;
  56. }
Success #stdin #stdout 0s 4756KB
comments (?)
stdin
copy 
3 2
1 1 2 3
2 2 3 1
stdout
copy 
4 1
https://ideone.com/XxdyLB
SPOJ QBSCHOOL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!