哈哈我又来填坑了!!



Description:

给你一个 个点, 条边的无向图,规定了起点 和终点 ,一个人从点 出发去 ,每一条 的最短路叫做关键路径,属于关键路径上的点称为关键点。假设每个单位时间可以移动 的长度。对于第 个点,如果其不是关键点,输出 "",否则假设从 时间为 ,输出在时间为 时,这个人可能在哪些位置上(PS:位置的定义和图的节点定义不同,不但可以站在节点上,还可以站在边上,比如一条长度为7的边,你可以站在其中长度为的地方而不仅仅是长度为 的两端)。



Solution:

首先跑一边最短路找出哪些点和哪些边在关键路径上,然后我们对于所有在关键路径上的边,假设两个端点为 ,那么我们就把 的答案区间加一。


Code:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int Mod=131071;

int N,S,T;
int M;
int dist[2010]={0};
int st=1,en=0;
int num=0;
int hash[2010]={0};
int dui[131100]={0};
int D[2010]={0};
int Sum[2010]={0};
int Sp=0;

struct bian_
{
    int st;
    int to;
    int next;
    int dis;
}bian[400010]={{0,0,0,0}};
int First[2010]={0};
int vis[2010]={0};

void Add(int p,int q,int r,int k)
{
    bian[k].next=First[p];
    bian[k].st=p;
    bian[k].to=q;
    bian[k].dis=r;
    First[p]=k;
    return;
}

void SPFA()
{
    memset(dist,0x3f3f3f3f,sizeof(dist));
    dui[++en]=S;
    dist[S]=0;
    num=1;
    for(;num>0;)
    {
        int u=dui[st];
        st=(st&Mod)+1;
        hash[u]=0;num--;
        for(int i=First[u];i!=0;i=bian[i].next)
        {
            int v=bian[i].to;
            if(dist[v]>dist[u]+bian[i].dis)
            {
                dist[v]=dist[u]+bian[i].dis;
                if(hash[v]==0)
                {
                    hash[v]=1;
                    if(dist[v]<dist[dui[st]])
                    {
                        st=((st+Mod-1)&Mod)+1;
                        dui[st]=v;
                    }
                    else
                    {
                        en=(en&Mod)+1;
                        dui[en]=v;
                    }
                    num++;
                }
            }
        }
    }
    return;
}

int Find(int k)
{
    for(int l=1,r=Sp;l<=r;)
    {
        int mid=(l+r)>>1;
        if(D[mid]==k) return mid;
        if(D[mid]<k) l=mid+1;
        else r=mid-1;
    }
    return 0;
}

int main()
{
    scanf("%d%d%d",&N,&S,&T);
    scanf("%d",&M);
    for(int i=1;i<=M;i++)
    {
        int p,q,r;
        scanf("%d%d%d",&p,&q,&r);
        Add(p,q,r,(i<<1)-1);
        Add(q,p,r,i<<1);
    }
    SPFA();
    for(int i=1;i<=N;i++)
        D[++Sp]=dist[i];
    sort(D+1,D+N+1);
    Sp=1;
    for(int i=2;i<=N;i++)
        if(D[i]!=D[i-1])
            D[++Sp]=D[i];
    for(int i=Sp+1;i<=N;i++) D[i]=0;
    en=1;
    dui[1]=T;
    for(int i=1;i<=en;i++)
    {
        int u=dui[i];
        for(int p=First[u];p!=0;p=bian[p].next)
        {
            int v=bian[p].to;
            if(dist[u]==dist[v]+bian[p].dis)
            {
                int L=Find(dist[v]),R=Find(dist[u]);
                vis[v]=vis[u]=1;
                Sum[L+1]++,Sum[R]--;
                if(hash[v]==0)
                    dui[++en]=v,hash[v]=1;
            }
        }
    }
    for(int i=1;i<=Sp;i++)
        Sum[i]+=Sum[i-1];
    for(int i=1;i<=N;i++)
        if(vis[i]==1)
            Sum[Find(dist[i])]++;
    for(int i=1;i<=N;i++)
    {
        int p=Find(dist[i]);
        printf("%d ",Sum[p]*vis[i]);
    }
    return 0;
}