hdu3631 Shortest Path(floyd 플러그인)

Shortest Path

제목:

n, m, q에게 n개의 점 m조 변의 q개를 표시하고 질문마다 두 가지 방식 0x를 묻습니다. 표시x를 표시하고 표시된 경우 ERROR을 출력합니다!At point x 1 x y는 출력 x에서 y까지의 최단 거리를 표시하고 x와 y 모두 및 최단 경로의 점을 표시해야 합니다. 만약에 x나 y가 출력 ERROR을 표시하지 않았다면!At path x to y, x에서 y 사이의 경로가 없으면 No such path 출력

Sample Input

5 10 10 1 2 6335 0 4 5725 3 3 6963 4 0 8146 1 2 9962 1 0 1943 2 1 2392 4 2 154 2 2 7422 1 3 9896 0 1 0 3 0 2 0 4 0 4 0 1 1 3 3 1 1 1 0 3 0 4 0 0 0

Sample Output

Case 1: ERROR! At point 4 ERROR! At point 1 0 0 ERROR! At point 3 ERROR! At point 4

분석:

삽입법, 또 못 들은 이름, 적어
우리가 점을 표시할 때마다 표시된 이 점을floyd 과정 중의 중간 노드 k로 하고 이 k로 모든 점 간의 최단로를 업데이트합니다

code：

#include
#include
#include
#include
#include
const int inf=0x3f3f3f3f;
const int inn=0x80808080;
using namespace std;
const int maxm=305;
int g[maxm][maxm];
int mark[maxm];
int n,m,q;
void init(){
     
    memset(g,inf,sizeof g);
    for(int i=0;i<n;i++)g[i][i]=0;
    memset(mark,0,sizeof mark);
}
void floyd(int k){
     
    for(int i=0;i<n;i++){
     
        for(int j=0;j<n;j++){
     
            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
        }
    }
}
int main(){
     
    int cas=1;
    while(scanf("%d%d%d",&n,&m,&q)!=EOF){
     
        if(!n&&!m&&!q)break;
        if(cas-1)puts("");
        init();
        for(int i=1;i<=m;i++){
     
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            g[a][b]=min(g[a][b],c);
        }
        printf("Case %d:
",cas++);
        while(q--){
     
            int d;
            scanf("%d",&d);
            if(d==0){
     
                int x;
                scanf("%d",&x);
                if(!mark[x]){
     
                    mark[x]=1;
                    floyd(x);
                }else{
     
                    printf("ERROR! At point %d
",x);
                }
            }else{
     
                int a,b;
                scanf("%d%d",&a,&b);
                if(!mark[a]||!mark[b]){
     
                    printf("ERROR! At path %d to %d
",a,b);
                }else{
     
                    if(g[a][b]==inf){
     
                        printf("No such path
");
                    }else{
     
                        printf("%d
",g[a][b]);
                    }
                }
            }
        }
    }
    return 0;
}