結果
| 問題 |
No.807 umg tours
|
| コンテスト | |
| ユーザー |
 asugen0402
|
| 提出日時 | 2019-05-17 13:04:13 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 301 ms / 4,000 ms |
| コード長 | 6,998 bytes |
| コンパイル時間 | 233 ms |
| コンパイル使用メモリ | 33,536 KB |
| 実行使用メモリ | 16,256 KB |
| 最終ジャッジ日時 | 2024-11-23 19:31:09 |
| 合計ジャッジ時間 | 4,432 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
ソースコード
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 内部定数
#define D_ON 1 // 汎用フラグ - ON
#define D_OFF 0 // 汎用フラグ - OFF
#define D_VTX_MAX 100000 // 最大頂点数
#define D_EDGE_MAX 200000 // 最大辺数
#define D_HEAP_MAX 1000000 // 最大ヒープ数
// 内部構造体 - 辺情報
typedef struct Edge {
int miVNo; // 接続先頂点 0～
int miLen; // 距離
struct Edge *mzpNext; // 次の辺情報
} Edge;
// 内部構造体 - 頂点情報
typedef struct Vtx {
Edge *mzpEdge; // 辺
long long mlMin1; // 最短距離 - チケット未使用
long long mlMin2; // 最短距離 - チケット使用
} Vtx;
// 内部構造体 - ヒープ情報
typedef struct Heap {
int miVNo; // 頂点 0～
long long mlLen; // 距離
int miTicket; // チケット使用・未使用
} Heap;
// 内部変数
static FILE *szpFpI; // 入力
static Vtx sz1Vtx[D_VTX_MAX]; // 頂点
static int siVCnt; // 頂点数
static Edge sz1Edge[D_EDGE_MAX * 2]; // 辺
static int siECnt; // 辺数
static Heap sz1Heap[D_HEAP_MAX]; // ヒープ
static int siHCnt; // ヒープ数
// 内部変数 - テスト用
#ifdef D_TEST
static int siRes;
static FILE *szpFpA;
static int siTNo;
#endif
// 出力
int
fOut(
char *pcpLine // <I> １行
)
{
char lc1Buf[1024];
#ifdef D_TEST
fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
if (strcmp(lc1Buf, pcpLine)) {
siRes = -1;
}
#else
printf("%s", pcpLine);
#endif
return 0;
}
// 辺 - 追加
int
fAddEdge(
int piVFNo // <I> 頂点 - 元 0～
, int piVTNo // <I> 頂点 - 先 0～
, int piLen // <I> 距離
)
{
sz1Edge[siECnt].miVNo = piVTNo;
sz1Edge[siECnt].miLen = piLen;
sz1Edge[siECnt].mzpNext = sz1Vtx[piVFNo].mzpEdge;
sz1Vtx[piVFNo].mzpEdge = &sz1Edge[siECnt];
siECnt++;
return 0;
}
// ヒープ - 比較 - 距離昇順
int
fHeapCmp(
int piNo1 // <I> 配列番号１ 0～
, int piNo2 // <I> 配列番号２ 0～
)
{
// 距離昇順
if (sz1Heap[piNo1].mlLen < sz1Heap[piNo2].mlLen) {
return -1;
}
else if (sz1Heap[piNo1].mlLen > sz1Heap[piNo2].mlLen) {
return 1;
}
return 0;
}
// ヒープ - 親子関係チェック
// 戻り値：[>=0]:変更した子の配列番号 [-1]:変更なし
int
fHeapChk(
int piPNo // <I> 親の配列番号 0～
)
{
int liRet;
// 最小値
int liMNo = piPNo;
// 左の子と比較
int liCNo = piPNo * 2 + 1;
if (liCNo < siHCnt) {
liRet = fHeapCmp(liMNo, liCNo);
if (liRet == 1) {
liMNo = liCNo;
}
}
// 右の子と比較
liCNo = piPNo * 2 + 2;
if (liCNo < siHCnt) {
liRet = fHeapCmp(liMNo, liCNo);
if (liRet == 1) {
liMNo = liCNo;
}
}
// 変更有無
if (piPNo == liMNo) {
return -1;
}
// 値の交換
Heap lzWork;
memcpy(&lzWork, &sz1Heap[liMNo], sizeof(Heap));
memcpy(&sz1Heap[liMNo], &sz1Heap[piPNo], sizeof(Heap));
memcpy(&sz1Heap[piPNo], &lzWork, sizeof(Heap));
return liMNo;
}
// ヒープ - キュー追加
int
fHeapEnqueue(
int piVNo // <I> 頂点 0～
, long long plLen // <I> 距離
, int piTicket // <I> チケット使用・未使用
)
{
int liRet;
// 最短距離 - チェック
if (piTicket == D_OFF) {
if (sz1Vtx[piVNo].mlMin1 >= 0) {
return 0;
}
}
else {
if (sz1Vtx[piVNo].mlMin2 >= 0) {
return 0;
}
}
// 末尾に追加
sz1Heap[siHCnt].miVNo = piVNo;
sz1Heap[siHCnt].mlLen = plLen;
sz1Heap[siHCnt].miTicket = piTicket;
siHCnt++;
// 親子関係チェック
int liNo = siHCnt - 1;
while (1) {
// 親の配列番号
liNo = (liNo - 1) / 2;
// 親子関係チェック
liRet = fHeapChk(liNo);
if (liRet < 0) {
break;
}
}
return 0;
}
// ヒープ - キュー取得
int
fHeapDequeue(
Heap *pzpRet // <O> 取得先
)
{
// データ数
if (siHCnt < 1) {
return -1;
}
// 取得
memcpy(pzpRet, &sz1Heap[0], sizeof(Heap));
siHCnt--;
// データ数
if (siHCnt < 1) {
return 0;
}
// 末尾を先頭へ
memcpy(&sz1Heap[0], &sz1Heap[siHCnt], sizeof(Heap));
// 親子関係チェック
int liNo = 0;
while (liNo >= 0) {
liNo = fHeapChk(liNo);
}
return 0;
}
// 実行メイン
int
fMain(
)
{
int i, liRet;
char lc1Buf[1024];
// 頂点数・辺数 - 取得
int liECnt;
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
sscanf(lc1Buf, "%d%d", &siVCnt, &liECnt);
// 辺 - 取得
for (i = 0; i < liECnt; i++) {
int liVNo1, liVNo2, liLen;
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
sscanf(lc1Buf, "%d%d%d", &liVNo1, &liVNo2, &liLen);
liVNo1--;
liVNo2--;
// 辺 - 追加
fAddEdge(liVNo1, liVNo2, liLen);
fAddEdge(liVNo2, liVNo1, liLen);
}
// 最短距離 - 初期化
for (i = 0; i < siVCnt; i++) {
sz1Vtx[i].mlMin1 = -1;
sz1Vtx[i].mlMin2 = -1;
}
// 頂点０
fHeapEnqueue(0, 0, D_OFF);
sz1Vtx[0].mlMin2 = 0;
// ヒープ - 取得
while (1) {
Heap lzHeap;
liRet = fHeapDequeue(&lzHeap);
if (liRet != 0) {
break;
}
// 最短距離 - 更新
if (lzHeap.miTicket == D_OFF) {
if (sz1Vtx[lzHeap.miVNo].mlMin1 >= 0) {
continue;
}
sz1Vtx[lzHeap.miVNo].mlMin1 = lzHeap.mlLen;
}
else {
if (sz1Vtx[lzHeap.miVNo].mlMin2 >= 0) {
continue;
}
sz1Vtx[lzHeap.miVNo].mlMin2 = lzHeap.mlLen;
}
// 辺でループ
Edge *lzpEdge = sz1Vtx[lzHeap.miVNo].mzpEdge;
while (lzpEdge != NULL) {
// 下位へ
fHeapEnqueue(lzpEdge->miVNo, (long long)lzpEdge->miLen + lzHeap.mlLen, lzHeap.miTicket);
// チケット使用
if (lzHeap.miTicket == D_OFF) {
fHeapEnqueue(lzpEdge->miVNo, lzHeap.mlLen, D_ON);
}
// 次の辺へ
lzpEdge = lzpEdge->mzpNext;
}
}
// 出力
for (i = 0; i < siVCnt; i++) {
sprintf(lc1Buf, "%lld\n", sz1Vtx[i].mlMin1 + sz1Vtx[i].mlMin2);
fOut(lc1Buf);
}
return 0;
}
// １回実行
int
fOne(
)
{
int liRet;
char lc1Buf[1024];
// データ - 初期化
memset(sz1Vtx, 0, sizeof(sz1Vtx)); // 頂点
siECnt = 0; // 辺数
siHCnt = 0; // ヒープ数
// 入力 - セット
#ifdef D_TEST
sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
szpFpI = fopen(lc1Buf, "r");
sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
szpFpA = fopen(lc1Buf, "r");
siRes = 0;
#else
szpFpI = stdin;
#endif
// 実行メイン
liRet = fMain();
// 残データ有無
#ifdef D_TEST
lc1Buf[0] = '\0';
fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
if (strcmp(lc1Buf, "")) {
siRes = -1;
}
#endif
// テストファイルクローズ
#ifdef D_TEST
fclose(szpFpI);
fclose(szpFpA);
#endif
// テスト結果
#ifdef D_TEST
if (siRes == 0) {
printf("OK %d\n", siTNo);
}
else {
printf("NG %d\n", siTNo);
}
#endif
return 0;
}
// プログラム開始
int
main()
{
#ifdef D_TEST
int i;
for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
siTNo = i;
fOne();
}
#else
fOne();
#endif
return 0;
}