NOJ——[1176] Exchange Rate

문제 설명You know, every country's currency has an exchange rate to another country.
For example, 'Dollir' : 'RNB' is 1 : 6.
And exchanging from one currency to another currency, it will have a wastage.
Now give some currency and their each wastage from one currency exchanges to another. For every currency, you should tell me when it exchanges to other currency and finally exchanges to itself, the minimum wastage it will cost.

입력This problem contains several cases.
The first line of each case is an integer N (2 <= N <= 100).
Then follows a decimal matrix(N * N). The Cell(i, j) indicates the wastage exchanging from ith currency to jth currency. (1.00 < Cell(i, j) <= 100.00).
You may consider that every currency can't exchange to itself directly, so every Cell(i, i) will be -1.

출력For each case, you may output N lines.
Each line is an decimal, indicates exchanging from ith currency and finally it exchanges to itself, the minimum wastage it will cost.
Two decimal places.

샘플 입력

4
-1 1.00 2.00 10.00
1.00 -1 2.00 30.00
1.00 1.00 -1 50.00
50.00 50.00 1.0 -1

샘플 출력

2.00
2.00
3.00
12.00

팁

출처

XadillaX

각 점이 자신의 최단로로 돌아가기를 구하다.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f

using namespace std;

double dp[105][105];

int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=n;j++)
		  {
  			scanf("%lf",&dp[i][j]);
  			if(i==j)
  			  dp[i][j]=inf;
  		  }
        for(int k=1;k<=n;k++)
           for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
               dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
        for(int i=1;i<=n;i++)
          printf("%.2f
",dp[i][i]);
	}
	return 0;
}