#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//#define BUILDING_N_MAX 200005
//#define ROAD_M_MAX 500005
#define BUILDING_N_MAX 7
#define ROAD_M_MAX 7
#define INF 1e16
struct _edge {
int start;
int end;
int weight;
int priv;
}EDGE[ROAD_M_MAX * 2]; // 무방향 간선은 2개의 방향성 간선으로 처리
int to[BUILDING_N_MAX]; // 출발정점 i 간선 중 마지막 출발한 간선의 번호
long long dist[BUILDING_N_MAX];
long long minimumWeight[BUILDING_N_MAX];
int qFront, qRear;
int Q[BUILDING_N_MAX * 30];
int inQ[BUILDING_N_MAX];
int main(void)
{
int T, buildingNumber, roadNumber;
freopen("input.txt", "r", stdin);
setbuf(stdout, NULL);
scanf("%d", &T);
for (int test_case = 1; test_case <= T; test_case++)
{
long long answer = 0;
scanf("%d %d", &buildingNumber, &roadNumber);
for (int j = 1; j <= buildingNumber; j++) {
// 모든 정점의 출발 기록은 아직 없으므로 -1 로 초기화
to[j] = -1;
// 모든 정점의 최단 거리 Distant는 최초 INF로 초기화
dist[j] = INF;
// 모든 정점의 weight 0 으로 초기화
minimumWeight[j] = 0;
}
int edgePosition = 0;
for (int i = 1; i <= roadNumber; i++) {
int s, e, w;
scanf("%d %d %d", &s, &e, &w);
// 무방향 간선은 2개의 방향성 간선으로 처리
++edgePosition;
EDGE[edgePosition].start = s;
EDGE[edgePosition].end = e;
EDGE[edgePosition].weight = w;
EDGE[edgePosition].priv = to[EDGE[edgePosition].start];
to[EDGE[edgePosition].start] = edgePosition;
++edgePosition;
EDGE[edgePosition].start = e;
EDGE[edgePosition].end = s;
EDGE[edgePosition].weight = w;
EDGE[edgePosition].priv = to[EDGE[edgePosition].start];
to[EDGE[edgePosition].start] = edgePosition;
}
// 시작시 Q 에 1번 정점을 넣어 1번 기준으로 시작
qFront = qRear = 0;
Q[qFront] = 1; inQ[1] = 0;
dist[1] = 0;
while (qFront <= qRear) {
// x -> y , weight
int x = Q[qFront++]; inQ[x] = 0;
// Q 에서 꺼내서 해당 정점에서 시작하는 EDGE 최단거리 확인
for (int edgePoint = to[x]; edgePoint != -1; edgePoint = EDGE[edgePoint].priv) {
int y = EDGE[edgePoint].end;
int w = EDGE[edgePoint].weight;
if (dist[y] > dist[x] + w) {
dist[y] = dist[x] + w;
minimumWeight[y] = w;
if (!inQ[y]) {
Q[++qRear] = y; inQ[y] = 1;
}
}
else if (dist[y] == dist[x] + w) {
// 최단 거리가 같은 경우에는 EDGE weight 더 적은 경로 선택
if (minimumWeight[y] > w)
minimumWeight[y] = w;
}
}
}
for (int k = 2; k <= buildingNumber; k++) {
answer += minimumWeight[k];
}
printf("#%d %lld\n", test_case, answer);
}
return 0;
}
댓글