NEU1685 All Pair Shortest Path（bfs+set优化）

February 16, 2016

题目链接

题意：输入一个 01 矩阵表示的有向图，D(i,j)表示 i 到 j 的最短路中的长度，求所有 D(i,j)*D(i,j)的和。

思路：枚举每个点作为源点，从源点出发 bfs，记录到源点的距离。如果用 vis[]来记录点是否到达的话，那么将是一个 n^3 的复杂度。因此可以用 set 维护源点未到达的点，每次队首点从 set 中遍历。需要注意的是，遍历到不能马上删除，如果这个点在当前迭代处后面时程序会跪，所以记录下要删除的点，it 遍历一遍之后一起删除。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
char pic[1005][1005];
long long dis[1005];

long long bfs(int a){
    memset(dis, -1, sizeof(dis));
    queue<int> q;
    set<int> s;
    set<int>::iterator it;
    dis[a] = 0;
    for(int i = 0; i < n; i++){
        if(i==a) continue;
        if(pic[a][i] == '1'){
            q.push(i);
            dis[i] = 1;
        }else
            s.insert(i);
    }

    int del[1005];
    int cnt = 0;
    while(!q.empty() && !s.empty()){
        int f = q.front();
        q.pop();
        for(it = s.begin(); it != s.end(); it++){
            int p = *it;
            if(pic[f][p] == '1'){
                q.push(p);
                dis[p] = dis[f]+1;
                del[cnt++] = p;
            }
        }
        for(int i = 0; i < cnt; i++)
            s.erase(del[i]);
    }

    long long sum = 0;
    for(int i = 0; i < n; i++){
        if(dis[i] == -1) sum += n*n;
        else sum += dis[i]*dis[i];
    }

    return sum;
}

int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d", &n) != EOF){
        for(int i = 0; i < n; i++)
            scanf("%s", pic[i]);
        long long ans = 0;

        for(int i = 0; i < n; i++){
            ans += bfs(i);
        }
        cout << ans << endl;

    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]