スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

AOJ 0189 Convenient Location

全点最短路問題です。
ワーシャル・フロイド法を用いて解きます。
cost[i][i]を0にするのをお忘れなく!


int cost[10][10];
int n,m;

int main(){
while(1){
cin >> n;
if(!n)break;

m = 0;
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(i==j){
cost[i][j] = 0;
}else{
cost[i][j] = INF;
}
}
}
for(int i=0;i int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(m m = max(x,y);
}
cost[x][y] = z;
cost[y][x] = z;
}
m++;

for(int k=0;k for(int i=0;i for(int j=0;j cost[i][j] = min(cost[i][j],cost[i][k]+cost[k][j]);
}
}
}

/*for(int i=0;i for(int j=0;j printf("%d%c",cost[i][j],j==m-1?'\n':' ');
}
}*/

int mini = INF;
int index;
for(int i=0;i int sum = 0;
for(int j=0;j sum += cost[i][j];
}
if(mini>sum){
mini = sum;
index = i;
}
}
cout << index << " " << mini << endl;
}
}



町の総数が10以下と十分に小さく、負の辺がないため
ひとつずつダイクストラ法で最短距離を求めることもできます。
うまく書けてるかはわかりませんがこんな感じ。

struct road{int to,cost;};

int main(){
while(1){
vector roads[10];
int d[10];
int n,m;

cin >> n;
if(!n)break;
m = 0;
for(int i=0;i int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(m m = max(x,y);
}
roads[x].push_back((road){y,z});
roads[y].push_back((road){x,z});
}
m++;

int minIndex;
int mini = INF;
for(int i=0;i priority_queue, greater

> que;
que.push(P(0,i));
fill(d,d+m,INF);
d[i] = 0;
while(que.size()){
P p = que.top(); que.pop();
int dist = p.first;
int pos = p.second;
if(d[pos] for(int j=0;j int to = roads[pos][j].to;
int cost = roads[pos][j].cost;
if(d[to]>d[pos]+cost){
d[to] = d[pos] + cost;
que.push(P(d[to],to));
}
}
}
int sum = 0;
for(int j=0;j //printf("%3d%c",d[j],j==m-1?'\n':' ');
sum += d[j];
}
if(mini>sum){
mini = sum;
minIndex = i;
}
}
cout << minIndex << " " << mini << endl;
}
}

スポンサーサイト
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。