[floyd 기록 경로]HDU 1385 최소 운송 비용
제목:한 곳 에서 택 시 를 타고 다른 곳 으로 가 는 데 비용 이 가장 적 게 드 는 경 로 를 찾 습 니 다.그 중에서 출발점 과 종점 을 제외 하고도중에 지나 가 는 역 은 Sample Input 5 0 3 22-1 4 0 5-1-1 22 5 0 9 20-1-1 9 0 4-1 20 4 0 5 17 3 1 3 5 2 4-1-1 0 Sample Output From 1 to 3:Path:1->5->4->3 Total cost:21 From 3 to 5:Path:3->4->5 Total cost:16 From 2 to 4:Path:2->1->5->4 Total cost:17
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 999999999 // 0x3fffffff ,
#define M 205
int dist[M][M], n, b[M], path[M][M];
void floyd ()
{
int i, j, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
path[i][j] = j; // , i j
for (k = 1; k <= n; k++)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
int tp = dist[i][k] + dist[k][j] + b[k];
// , + b[k],
if (tp < dist[i][j])
dist[i][j] = tp, path[i][j] = path[i][k];
else if (tp == dist[i][j] && path[i][k] < path[i][j])
path[i][j] = path[i][k]; //
}
}
}
}
int main()
{
int i, j, u, v, tp;
while (scanf ("%d", &n), n)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf ("%d", dist[i]+j);
if (dist[i][j] == -1)
dist[i][j] = inf;
}
}
for (i = 1; i <= n; i++)
scanf ("%d", b+i);
floyd();
while (scanf ("%d%d", &u, &v), (u != -1 || v != -1))
{
printf ("From %d to %d :
", u, v);
printf ("Path: %d", u);
tp = u;
while (u != v)
{
printf ("-->%d", path[u][v]);
u = path[u][v];
}
printf ("
Total cost : %d
", dist[tp][v]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.