HDU 4460 SPFA

HDU 4460 제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=4460 제목:일부 점(<=1e3)일부 변(<=1e5).임의의 두 점 의 최대 거 리 는 얼마 입 니까?연결 되 지 않 으 면 출력-1.사고:원래 spfa 가 잘못 되 었 습 니 다.우선 대기 열 을 dij 라 고 부 릅 니 다.사용 하지 않 는 것 은 spfa 라 고 부 릅 니 다.가끔 은 우선 대기 열 이 느 릴 때 가 있 습 니 다.O(logn)의 복잡 도가 거기에 있 고 한 점 은 서로 다른 거리 값 이 여러 번 들 어 오기 때문에 최 단 로 는 항상 우선 대기 열 에 올 라 갈 수 없습니다.복 현 했 을 때 복잡 도 를 계산 해 보 니 O(M)가 믿 을 만하 다 고 생각 했 습 니 다.이런 단순 한 폭력 매 거 진 은 지나 갈 수 없다 고 생각 했 습 니 다.그래서 유연성 측면 에서 해 보 았 습 니 다.두 시간 후에 문 제 를 버 렸 습 니 다.사실은 데이터 물 일 수도 있 고 순수한 spfa 도 지나 갈 수 있 습 니 다.전체 문제 가 되 었 는데 왜 한 발 안 해 봐...............................................................................원본 코드:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int MAXN = 1000 + 5;
#define inf (1000000007)
int d[MAXN];
struct D
{
    int u, d;
    bool operator < (const D&rbs)const{
        return d < rbs.d;
    }
};
vector<int>lin[MAXN];
queue<int>que;
char s1[MAXN], s2[MAXN];
map<string, int>mm;
int ans;
int vis[MAXN];
int n, m;
void bfs(int u)
{
// printf("org u = %d
", u);
    for(int i = 1 ; i <= n ; i++)
        d[i] = inf, vis[i] = 0;
    while(!que.empty()) que.pop();
    vis[u] = 1, d[u] = 0, que.push(u);
    while(!que.empty()){
        u = que.front();  que.pop();
// printf("u = %d
", u);
        vis[u] = 0;
        for(int j = 0 ; j < (int)lin[u].size() ; j++){
            int v = lin[u][j];
            if(d[v] > d[u] + 1){
// printf("v = %d
", v);
                d[v] = d[u] + 1;
                if(vis[v] == 0) que.push(v), vis[v] = 1;
            }
        }
    }
// for(int i = 1 ; i <= n ; i++) printf("d[%d] = %d
", i, d[i]);
    for(int i = 1 ; i <= n ; i++)
        ans = max(ans, d[i]);
}
int main()
{
// freopen("HDU 4460.in", "r", stdin);
    while(scanf("%d", &n) != EOF && n){
        mm.clear();
        for(int i = 1 ; i <= n ; i++){
            scanf("%s", s1);
            mm[s1] = i;
            lin[i].clear();
        }
        scanf("%d", &m);
        for(int i = 1 ; i <= m ; i++){
            scanf("%s%s", s1, s2);
// printf("first = %d, second = %d
", mm[s1], mm[s2]);
            lin[mm[s1]].push_back(mm[s2]);
            lin[mm[s2]].push_back(mm[s1]);
        }
        ans = 0;
        for(int i = 1 ; i <= n ; i++)
            bfs(i);
        if(ans == inf)   printf("-1
");
        else    printf("%d
", ans);
    }
    return 0;
}