PKU 2394 Checking an Alibi
http://poj.org/problem?id=2394
指定されたノードのうち、ノード1から距離がM以下のものを列挙するというような問題。
ダイクストラやるだけ。
なんですが、コストの初期化をさぼったせいで1WA。
400問解いたあたりでも感じたような気がするんですが、開くたびに解けない感覚に襲われてます、他のonline judgeに逃げたいです。
vector<PI> G[500]; bool vis[500]; int cost[500]; main(){ int f,p,c,m; cin>>f>>p>>c>>m; rep(i,f)cost[i]=m+1; rep(i,p){ int f1,f2,t; cin>>f1>>f2>>t; --f1,--f2; G[f1].pb(mp(f2,t)); G[f2].pb(mp(f1,t)); } priority_queue<PI> q; q.push(mp(0,0)); while(!q.empty()){ int cc=-q.top().F,v=q.top().S; q.pop(); if(vis[v])continue; vis[v]=true; cost[v]=cc; rep(i,SZ(G[v])){ int to=G[v][i].F; if(vis[to])continue; q.push(mp(-cc-G[v][i].S,to)); } } set<int> ans; rep(i,c){ int lc; cin>>lc; --lc; if(cost[lc]<=m)ans.insert(i+1); } cout<<SZ(ans)<<endl; FOR(iter,ans)cout<<*iter<<endl; }