现在的位置: 首页 > 综合 > 正文

NOJ——[1176] Exchange Rate

2019年02月16日 ⁄ 综合 ⁄ 共 1330字 ⁄ 字号 评论关闭
  • 问题描述
  • 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\n",dp[i][i]);
}
return 0;
}

抱歉!评论已关闭.