AOJ 0545: Party
" 入力例 2 において,あなたには友達はいない."
単一始点最短路を求める問題。
普通にダイクストラ法やワーシャルフロイド法するのは面白くないので少しだけ違う解き方をしました。
想定解法とあまり変わらないみたいです。
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int n,m,s[500],l[10000],r[10000]; int main(){ while(cin>>n>>m,n){ memset(s,0,sizeof(s)); s[0] = 3; for(int i = 0; i < m; i++){ cin>>l[i]>>r[i]; l[i]--; r[i]--; } for(int i = 0; i < 2; i++){ for(int j = 0; j < m; j++){ int a = l[j],b = r[j]; s[a] = max(s[a],s[b]-1); s[b] = max(s[b],s[a]-1); } } int ans = -1; for(int i = 0; i < n; i++){ if(s[i])ans++; } cout<<ans<<endl; } return 0; }