1 条题解

  • 0
    @ 2025-6-21 16:15:49

    #include<bits/stdc++.h> using namespace std; int n,m,k,t,x,y,z,id; struct o{ int x,y; }; bool operator <(o x,o y){ return x.x>y.x; } int dis[300005],a[300005],ans; int vis[300005]; int last[300005],v[300005],pre[300005],d[300005]; priority_queue<o> q; void add(int x,int y,int z){ v[++id]=y,pre[id]=last[x],d[id]=z; last[x]=id; } void dij(int x){ memset(dis,0x3f,sizeof dis); dis[1]=0; q.push({0,x}); while(!q.empty()){ int u=q.top().y; q.pop(); if(vis[u])continue; //for(int j=1;j<=n;j++)if(vis[j]==0&&dis[j]<dis[u])u=j; vis[u]=1; for(int j=last[u];j;j=pre[j])if(vis[v[j]]==0&&dis[u]+d[j]<dis[v[j]])dis[v[j]]=dis[u]+d[j],q.push({dis[v[j]],v[j]}); } } int main(){ freopen("alibi.in","r",stdin); freopen("alibi.out","w",stdout); cin>>n>>m>>k>>t; for(int i=0;i<m;i++)cin>>x>>y>>z,add(x,y,z),add(y,x,z); for(int i=1;i<=k;i++)cin>>a[i]; dij(1); for(int i=1;i<=k;i++)if(dis[a[i]]<=t)ans++; cout<<ans<<"\n"; for(int i=1;i<=k;i++)if(dis[a[i]]<=t)cout<<i<<"\n"; return 0; }

    信息

    ID
    615
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    8
    已通过
    3
    上传者