23132 문제 A 관건 적 인 경로

문제 A: 관건 적 인 경로
시간 제한: 1 Sec  메모리 제한: 128 MB 제출: 43  해결: 15
 
제목 설명
설명:
그림 의 연결 변 에 있 는 데 이 터 는 그 가중치 를 나타 내 고 가중치 가 있 는 그림 을 네트워크 라 고 합 니 다.위의 그림 은 정점 집합 (a, b, c, d, e) 변 집합 과 그 가중치 (시점, 종점) 로 묘사 할 수 있다. 가중치): a b 3  a c 2   b d 5  c d 7   c e 4  d e 6            
 
  네트워크 의 원점 은 입 도 0 의 정점 이 고, 외환 점 은 출 도 0 의 정점 이다. 네트워크 의 관건 적 인 경 로 는 원점 에서 외환 점 까지 의 모든 경로 중에서 가장 큰 경로 길 이 를 가 진 경 로 를 말한다. 위의 그림 에서 관건 적 인 경 로 는 a - > c - > d - > e 이 며, 그 가중치 의 합 은 관건 적 인 경로 의 길 이 는 15 이다.
  이 문제 의 요 구 는 제 시 된 네트워크 의 인접 행렬 에 따라 이 네트워크 의 관건 적 인 경로 와 길 이 를 구 하 는 것 이다.
 
입력
첫 번 째 줄 에 정수 n (1 < = n < = 5) 을 입력 하면 테스트 데이터 의 수량, 즉 그림 의 수량 을 대표 합 니 다.
두 번 째 줄 은 x (1 < = x < = 15) 를 입력 하면 정점 개 수 를 나타 내 고 y (1 < = y < = 19) 는 변 의 개 수 를 나타 낸다.
세 번 째 줄 은 그림 의 정점 집합 을 제시 하고 모두 x 개의 소문 자 는 정점 을 나타 낸다.
다음 줄 마다 한 변 의 시작 점 과 종점 과 그 가중치 를 제시 하고 빈 칸 으로 구분 하 며 각 줄 은 한 변 을 대표 합 니 다.
출력
첫 번 째 출력 은 그림 의 관건 적 인 경로 입 니 다.
두 번 째 출력 은 관건 적 인 경로 의 길이 입 니 다.
각 행렬 은 위의 두 출력 에 대응 하고 두 출력 은 같은 줄 에서 빈 칸 으로 간격 을 두 며 각 행렬 의 출력 은 한 줄 을 차지한다.
 
샘플 입력

2
5 6
abcde
a b 3
a c 2
b d 5
c d 7
c e 4
d e 6
4 5
abcd
a b 2
a c 3
a d 4
b d 1
c d 3

샘플 출력

(a,c) (c,d) (d,e) 15
(a,c) (c,d) 6

제시 하 다.
저자: 양 청 청 청
경험 총화
이 문 제 는 전형 적 인 관건 적 인 경 로 를 구 하 는 문제 이기 도 합 니 다. 주의해 야 할 것 은 e [i] = l [i] 에 저장 하고 마지막 에 원점 을 찾 아 출력 하 는 것 입 니 다. 그렇지 않 으 면 출력 하 는 경로 순서 가 요구 에 부합 되 지 않 고 다른 것 은 아무것도 아 닙 니 다.  자다 자다
정확 한 코드

#include 
#include 
#include 
#include 
#include 
#include