P1083 （C++代码）

解题思路:





注意事项:





参考代码:、

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<queue>  
   
using namespace std;  
   
typedef struct{  
    int v;  
    int step;  
}node;  
   
vector <int> g[100005];  
int n, m, s, eat, ans;  
int visit[100005];  
   
void init();  
void read();  
void bfs(int s);  
int main(){  
    scanf("%d %d %d", &n, &m, &s);  
    scanf("%d", &eat);  
    init();  
    read();  
       
    memset(visit, 0, sizeof(visit));  
    bfs(s);  
       
    printf("%d\n", ans + eat);  
    return 0;  
}  
   
void bfs(int s){  
    int i, cur;  
    queue <node> Q;  
    node p, q;  
       
    p.v = s;  
    p.step = 1;  
    visit[s] = 1;  
    Q.push(p);  
       
    while(!Q.empty()){  
        q = Q.front();  
        Q.pop();  
       
        cur = q.v;  
        for(i = 0; i < g[cur].size(); i++){  
            p.v = g[cur][i];  
            if(!visit[p.v]){  
                p.step = q.step + 1;  
                Q.push(p);  
                visit[p.v] = 1;  
            }  
        }  
        ans = q.step;  
    }     
}  
   
void read(){  
    int i, j, k;  
       
    for(i = 0; i < m; i++){  
        scanf("%d %d", &j, &k);  
        g[j].push_back(k);  
        g[k].push_back(j);  
    }  
}  
   
void init(){  
    int i;  
    for(i = 1; i <= n; i++)  
        g[i].clear();  
}