이후 새로 추가되는 도로를 1개씩 추가하여 최단 거리가 변경되는지 체크하는게 제 알고리즘의 내용인데요..
혹시 잘못된 알고리즘인지... 아니면 개선의 여지가 있는 알고리즘 인지..
고수님들의 조언을 부탁드립니다.
감사합니다. 좋은 하루 보내세요!
#include <stdio.h>//#include <time.h>#define MAX_COST 100000#define NUM 200intTC;intV;// 도시 수로 고정값 2~200intMM;// 현재 도로intNN;// 미래 도로 0<=M+N<=1000intg[NUM][NUM];intd[NUM][NUM];intp[NUM][NUM];// function 의 overflow 가 있는것 같은데,, 문제를 해결할줄 몰라서 전역변수로 선언...intld[NUM][NUM];intlp[NUM][NUM];intN[NUM];intNi=0;intdi[NUM];intpa[NUM];intdijkstra(void){intenhanced=0;// initfor(inti=0;i<V;i++){for(intj=0;j<V;j++){ld[i][j]=0;lp[i][j]=-1;}}// 기존 다익스트라를 for loop 으로 모든 src 에 대해 진행for(inti=0;i<V;i++){// i 는 시작점// initfor(intj=0;j<V;j++){N[j]=0;di[j]=g[i][j];pa[j]=-1;}N[i]=1;Ni=1;while(Ni<V){intlow=999999;intlowi=-1;// find shortest pathfor(intj=0;j<V;j++){if(di[j]!=-1&&di[j]!=0&&N[j]!=1&&low>di[j]){low=di[j];lowi=j;}}N[lowi]=1;Ni++;// update shortest pathfor(intj=0;j<V;j++){if(g[lowi][j]!=-1&&g[lowi][j]!=0&&N[j]!=1){if(di[j]==-1||di[j]==0||di[j]>di[lowi]+g[lowi][j]){di[j]=di[lowi]+g[lowi][j];pa[j]=lowi;}}}}// ld, lp 에 di, pa 를 입력for(intj=0;j<V;j++){ld[i][j]=di[j];lp[i][j]=pa[j];}}// TODO ; return 1 if d[][] is updated, 0 if there is no updatefor(inti=0;i<V;i++){for(intj=0;j<V;j++){if(d[i][j]>ld[i][j]||(d[i][j]==-1&&ld[i][j]!=-1))enhanced=1;d[i][j]=ld[i][j];}}if(enhanced>0)return1;elsereturn0;}intmain(void){//clock_t st = clock();//freopen("input.txt", "r", stdin);//setbuf(stdout, NULL);scanf("%d",&TC);for(inti=0;i<TC;i++){intresult=0;// initfor(intj=0;j<NUM;j++){for(intk=0;k<NUM;k++){g[j][k]=-1;}g[j][j]=0;for(intk=0;k<NUM;k++){d[j][k]=-1;p[j][k]=-1;}}// inputscanf("%d %d %d",&V,&MM,&NN);for(intj=0;j<MM;j++){intsrc,dest,cost;scanf("%d %d %d",&src,&dest,&cost);g[src][dest]=cost;g[dest][src]=cost;}// 현재 g 로 기준 d[] 만듦dijkstra();for(intj=1;j<=NN;j++){intsrc,dest,cost;scanf("%d %d %d",&src,&dest,&cost);g[src][dest]=cost;g[dest][src]=cost;// dijkstra 로 d[]' 만듦result+=dijkstra();}printf("%d\n",NN-result);}//printf("time : %d\n",clock()-st);return0;}
gloryof11
PROMISES
안녕하세요 다익스트라 알고리즘을 공부하고 PROMISES 문제를 풀어 보았습니다.
하지만, 시간 초과가 발생하여 답답한 상황에 있습니다;;
주어진 도로로 최단 거리를 구해 놓고,
이후 새로 추가되는 도로를 1개씩 추가하여 최단 거리가 변경되는지 체크하는게 제 알고리즘의 내용인데요..
혹시 잘못된 알고리즘인지... 아니면 개선의 여지가 있는 알고리즘 인지..
고수님들의 조언을 부탁드립니다.
감사합니다. 좋은 하루 보내세요!
8년 전