[플로이드 분치] 마늘의 길 2016 재경기.바이두 지도의 실시간 도로 상황

3834 단어 최단로나누어 다스리다
대y분치
만약 l=r, n2가 디스 수조를 한 번 훑어보고 답을 기록한다면 [l,r] 구간으로 처리한다.
그렇지 않으면 [l,mid]의 가장자리를 그림에 넣고 [mid+1,r]로 돌아가고 [mid+1,r]의 가장자리를 그림에 넣고 [l,mid]로 돌아간다
#include 
#include 
#include 
#include 

using namespace std;

const int N=310,inf=1<<29;

typedef long long ll;

int n;
int dis[N][N];
ll ans;

void solve(int l,int r){
    if(l==r){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j && i!=l && j!=l) ans+=dis[i][j]==inf?-1:dis[i][j];
        return ;
    }
    int mid=l+r>>1,tmp[N][N];
    memcpy(tmp,dis,sizeof(tmp));
    for(int k=l;k<=mid;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    solve(mid+1,r);
    memcpy(dis,tmp,sizeof(dis));
    for(int k=mid+1;k<=r;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    solve(l,mid);
    memcpy(dis,tmp,sizeof(dis));
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&dis[i][j]);
            if(!~dis[i][j]) dis[i][j]=inf; 
        }
    solve(1,n);
    cout<return 0;
}
leetcode_Sort List
마지막 커밋을 삭제/삭제하시겠습니까?이게 어떻게 된 거야?

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage