学步园

dijkstra （优先队列优化）

找一个无向图到一点最短距离为l的点的个数（该点可以在边上）

分在点上和边上2种进行计数， 在边上的则要对该边的2个顶点讨论一下

//单源最短路 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

const int maxn=100000+123;
const int inf=0x5fffffff;

struct Edge{
    int v, w, next;   
}edge[maxn*2];
int head[maxn], cnt;

struct Node{
    int u, w;
    bool operator < (Node a)const
    {
        return w > a.w;
    }
};

void addedge(int u, int v, int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

int dist[maxn];
void Dijkstra(int s, int n)//0到n-1 s是源点 
{
    for (int i=0; i<n; ++i)
        dist[i]=inf;
    dist[s]=0;
    priority_queue<Node> q;
    Node cur;
    cur.u=s; cur.w=0;
    q.push(cur);
    while (!q.empty())
    {
        cur=q.top();
        q.pop();
        if(dist[cur.u]<cur.w)continue;
        for (int p=head[cur.u]; ~p; p=edge[p].next)
            if(dist[edge[p].v]>dist[cur.u]+edge[p].w)
            {
                dist[edge[p].v]=dist[cur.u]+edge[p].w;
                Node tmp;
                tmp.u=edge[p].v;
                tmp.w=dist[edge[p].v];
                q.push(tmp);
            }
    }
    //for (int i=0; i<n; ++i)cout << dist[i] << " ";
    //cout << endl;
}

void init ()
{
    cnt=0;
    memset (head, -1, sizeof(head));
}

void solve()
{
    init();
    int n, m, s, u, v, w, l;
    cin >> n >> m >>s;
    s--;
    for (int i=0; i<m; ++i)
    {
        cin >> u >> v >> w;
        u--, v--;
        addedge(u, v, w);
        addedge(v, u, w);
    }
    cin >> l;
    Dijkstra(s, n);
    int ans=0;
    for (int i=0; i<n; ++i)if(dist[i]==l)ans++;
    for (int i=0; i<cnt; i+=2)
    {
        w=edge[i].w;
        u=edge[i].v;
        v=edge[i^1].v;
        if(dist[u]>dist[v])u^=v^=u^=v;
        if(dist[u]<l && dist[v]>=l && dist[u]+w>l)ans++;
        if(dist[u]<l && dist[v]<l && (dist[u]+dist[v]+w)>(2*l) )ans+=2;
        if(dist[u]<l && dist[v]<l && (dist[u]+dist[v]+w) == (2*l) )ans++;
    }
    printf("%d\n", ans);
}

int main ()
{
    solve();
    return 0;
}