codeforces 144 D Missile Silos(最短)

19381 ワード

転載は出典を明記してください.  http://www.cnblogs.com/fraud/            ——by fraud
 
Missile Silos
A country called Berland consists of n cities, numbered with integer numbers from 1 to n. Some of them are connected by bidirectional roads. Each road has some length. There is a path from each city to any other one by these roads. According to some Super Duper Documents, Berland is protected by the Super Duper Missiles. The exact position of the Super Duper Secret Missile Silos is kept secret but Bob managed to get hold of the information. That information says that all silos are located exactly at a distance l from the capital. The capital is located in the city with number s.
The documents give the formal definition: the Super Duper Secret Missile Silo is located at some place (which is either city or a point on a road) if and only if the shortest distance from this place to the capital along the roads of the country equals exactly l.
Bob wants to know how many missile silos are located in Berland to sell the information then to enemy spies. Help Bob.
Input
The first line contains three integers n, m and s (2 ≤ n ≤ 105, 1 ≤ s ≤ n) — the number of cities, the number of roads in the country and the number of the capital, correspondingly. Capital is the city no. s.
Then m lines contain the descriptions of roads. Each of them is described by three integers vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 1 ≤ wi ≤ 1000), where vi, ui are numbers of the cities connected by this road and wi is its length. The last input line contains integer l (0 ≤ l ≤ 109) — the distance from the capital to the missile silos. It is guaranteed that:
  • between any two cities no more than one road exists;
  • each road connects two different cities;
  • from each city there is at least one way to any other city by the roads.

  • Output
    Print the single number — the number of Super Duper Secret Missile Silos that are located in Berland.
    Sample test(s)
    Input
    4 6 1
    1 2 1
    1 3 3
    2 3 1
    2 4 1
    3 4 1
    1 4 2
    2

    Output
    3

    Input
    5 6 3
    3 1 1
    3 2 1
    3 4 1
    3 5 1
    1 2 6
    4 5 8
    4

    Output
    3

    Note
    In the first sample the silos are located in cities 3 and 4 and on road (1, 3) at a distance 2 from city 1 (correspondingly, at a distance 1 from city 3).
    In the second sample one missile silo is located right in the middle of the road (1, 2). Two more silos are on the road (4, 5) at a distance 3 from city 4 in the direction to city 5 and at a distance 3 from city 5 to city 4.
    タイトル:
    図を1枚与えて、図の上のすべてのs点までの距離がdのいくつかの点があることを聞きます.
     
    一度最短絡し,sからすべての点までの最短距離を得た.次に、各エッジを列挙し、エッジに要求を満たす点があるかどうかを統計します.

      1 #include <iostream>
    
      2 #include <sstream>
    
      3 #include <ios>
    
      4 #include <iomanip>
    
      5 #include <functional>
    
      6 #include <algorithm>
    
      7 #include <vector>
    
      8 #include <string>
    
      9 #include <list>
    
     10 #include <queue>
    
     11 #include <deque>
    
     12 #include <stack>
    
     13 #include <set>
    
     14 #include <map>
    
     15 #include <cstdio>
    
     16 #include <cstdlib>
    
     17 #include <cmath>
    
     18 #include <cstring>
    
     19 #include <climits>
    
     20 #include <cctype>
    
     21 using namespace std;
    
     22 #define XINF INT_MAX
    
     23 #define INF 0x3FFFFFFF
    
     24 #define MP(X,Y) make_pair(X,Y)
    
     25 #define PB(X) push_back(X)
    
     26 #define REP(X,N) for(int X=0;X<N;X++)
    
     27 #define REP2(X,L,R) for(int X=L;X<=R;X++)
    
     28 #define DEP(X,R,L) for(int X=R;X>=L;X--)
    
     29 #define CLR(A,X) memset(A,X,sizeof(A))
    
     30 #define IT iterator
    
     31 typedef long long ll;
    
     32 typedef pair<int,int> PII;
    
     33 typedef vector<PII> VII;
    
     34 typedef vector<int> VI;
    
     35 #define MAXN 100100
    
     36 vector<PII> Map[MAXN];
    
     37 
    
     38 //      
    
     39 void init() { REP(i,MAXN) Map[i].clear(); }
    
     40 
    
     41 //  s             dis  
    
     42 int dis[MAXN];
    
     43 void dijkstra(int s)
    
     44 {
    
     45     REP(i,MAXN){dis[i]=i==s?0:INF;}
    
     46     int vis[MAXN] = {0};
    
     47     priority_queue<PII, vector<PII>, greater<PII> > q;
    
     48     q.push(MP(0,s));
    
     49     while(!q.empty())
    
     50     {
    
     51         PII p = q.top(); q.pop();
    
     52         int x = p.second;
    
     53         if(vis[x])continue;
    
     54         vis[x] = 1;
    
     55         for(vector<PII>::iterator it = Map[x].begin(); it != Map[x].end(); it++)
    
     56         {
    
     57             int y = it->first;
    
     58             int d = it->second;
    
     59             if(!vis[y] && dis[y] > dis[x] + d)
    
     60             {
    
     61                 dis[y] = dis[x] + d;
    
     62                 q.push(MP(dis[y],y));
    
     63             }
    
     64         }
    
     65     }
    
     66 }
    
     67 
    
     68 struct node
    
     69 {
    
     70     int u,v,d;
    
     71 }edge[MAXN];
    
     72 int main()
    
     73 {
    
     74     ios::sync_with_stdio(false);
    
     75     int n,m,s;
    
     76     while(cin>>n>>m>>s)
    
     77     {
    
     78         int u,v,d;
    
     79         init();
    
     80         for(int i=0;i<m;i++)
    
     81         {
    
     82             cin>>u>>v>>d;
    
     83             u--;
    
     84             v--;
    
     85             Map[u].PB(MP(v,d));
    
     86             Map[v].PB(MP(u,d));
    
     87             edge[i].u=u;
    
     88             edge[i].v=v;
    
     89             edge[i].d=d;
    
     90         }
    
     91         int l;
    
     92         cin>>l;
    
     93         s--;
    
     94         dijkstra(s);
    
     95         int ans=0;
    
     96         for(int i=0;i<n;i++)
    
     97         {
    
     98             if(dis[i]==l)ans++;
    
     99         }
    
    100         for(int i=0;i<m;i++)
    
    101         {
    
    102             u=edge[i].u;
    
    103             v=edge[i].v;
    
    104             d=edge[i].d;
    
    105             if(dis[u]>dis[v])swap(u,v);
    
    106             if(dis[v]-dis[u]==d)
    
    107             {
    
    108                 if(l>dis[u]&&l<dis[v])ans++;
    
    109             }
    
    110             else
    
    111             {
    
    112                 int x=l-dis[u];
    
    113                 if(x<=0)continue;
    
    114                 if(x>d)continue;
    
    115                 if(dis[v]>l&&x<d)
    
    116                 {
    
    117                     ans++;
    
    118                     continue;
    
    119                 }
    
    120                 if(dis[v]==l&&x<d)
    
    121                 {
    
    122                     ans++;
    
    123                     continue;
    
    124                 }
    
    125                 int y=l-dis[v];
    
    126                 if(x+y==d)
    
    127                 {
    
    128                     ans++;
    
    129                     continue;
    
    130                 }
    
    131                 if(x<d-y)ans++;
    
    132                 if(y<d-x)ans++;
    
    133             }
    
    134         }
    
    135         cout<<ans<<endl;
    
    136     }
    
    137         
    
    138             
    
    139     return 0;
    
    140 }

    コード君