题目链接：http://codeforces.com/problemset/problem/144/D

思路：首先spfa求出中心点S到其余每个顶点的距离，统计各顶点到中心点的距离为L的点，然后就是要统计在边上的点了，可以枚举边（这里边的数量最多也就100000条)，对于枚举的某条边，如果它的其中某个端点到S的距离记过这条边，也就是满足一下这个条件：d1 + w == d2 || d2 + w == d1，那么边上符合要求的点最多只有一个，否则，就要判断d1,d2的关系，对于求出的边上的某个符合要求的顶点，还要看对于另一端是否也符合最短路径的要求（一开始没考虑这个，wa了一发）。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#define REP(i, a, b) for (int i = (a); i < (b); ++i)

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;

const int MAX_N = (100000 + 100);

int N, M, S, L, ans, dist[MAX_N];

int vis[MAX_N], flag[MAX_N];

struct Node {

    int v, w;

    Node() {}

    Node(int _v, int _w) : v(_v), w(_w) {}

};

vector<Node > g[MAX_N];

struct Edge {

    int u, v, w;

} edge[MAX_N << 1];

void spfa(int st)

{

    memset(dist, 0x3f, sizeof(dist));

    memset(vis, 0, sizeof(vis));

    dist[st] = 0;

    queue<int > que;

    que.push(st);

    while (!que.empty()) {

        int u = que.front(); que.pop();

        vis[u] = 0;

        REP(i, 0, (int)g[u].size()) {

            int v = g[u][i].v, w = g[u][i].w;

            if (dist[u] + w < dist[v]) {

                dist[v] = dist[u] + w;

                if (!vis[v]) { vis[v] = 1; que.push(v); }

            }

        }

    }

}

int main()

{

    while (cin >> N >> M >> S) {

        FOR(i, 1, N) g[i].clear();

        FOR(i, 1, M) {

            int u, v, w; cin >> u >> v >> w;

            g[u].push_back(Node(v, w));

            g[v].push_back(Node(u, w));

            edge[i].u = u, edge[i].v = v, edge[i].w = w;

        }

        cin >> L;

        spfa(S);

        memset(flag, 0, sizeof(flag));

        ans = 0;

        FOR(i, 1, N) if (dist[i] == L) ++ans;

        FOR(i, 1, M) {

            int d1 = dist[edge[i].u], d2 = dist[edge[i].v], w = edge[i].w;

            if (d1 + w == d2 || d2 + w == d1) {

                if ((d1 < L && d2 > L) || (d2 < L && d1 > L)) ++ans;

            } else {

                if (d1 < L && d1 + w > L){

                    int dd = d1 + w - L;

                    if (d2 + dd >= L) ++ans;

                }

                if (d2 < L && d2 + w > L) {

                    int dd = d2 + w - L;

                    if (d1 + dd >= L) ++ans;

                }

                if (2 * L == d1 + d2 + w) --ans;

            }

        }

        cout << ans << endl;

    }

    return 0;

}