N-Tram-最短spfa()アルゴリズム
3765 ワード
Think:1知識点:最短_spfa()アルゴリズム2思考:題意を理解して図を構築する
vjudgeタイトルリンク
以下、Acceptedコード
vjudgeタイトルリンク
以下、Acceptedコード
#include
#include
#include
#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e2 + 4;
int n, e[N][N], vis[N], dis[N];
void spfa(int x);
int main(){
int x, y, k, i, j, v;
while(~scanf("%d %d %d", &n, &x, &y)){
memset(e, inf, sizeof(e));
for(i = 1; i <= n; i++){
scanf("%d", &k);
for(j = 0; j < k; j++){
scanf("%d", &v);
if(!j)
e[i][v] = 0;
else
e[i][v] = 1;
}
}
spfa(x);
if(dis[y] != inf)
printf("%d
", dis[y]);
else
printf("-1
");
}
return 0;
}
void spfa(int x){
queue <int> q;
while(!q.empty()){
q.pop();
}
memset(dis, inf, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[x] = 0, vis[x] = 1;
q.push(x);
while(!q.empty()){
int t1 = q.front();
q.pop();
vis[t1] = 0;
for(int i = 1; i <= n; i++){
if(dis[t1] + e[t1][i] < dis[i]){
dis[i] = dis[t1] + e[t1][i];
if(!vis[i]){
vis[i] = 1;
q.push(i);
}
}
}
}
}