返回列表 發帖

Rank: 9Rank: 9Rank: 9
1# 跳轉到 » 倒序看帖
打印
tT
may發表於 2025-1-29 21:57 | 只看該作者

202412潛力3-超能星球 (Planet)

超能星球 (Planet) 問題敘述 在競程宇宙中，AC超人和他的英雄夥伴住在一顆特殊的星球上。這顆星球是正十二面體的形狀，正十二面體一共有12個面、30條邊和20個頂點。星球的外觀和展開圖分別如下所示。

由於這個星球不是球體，星球表面每個位置重力方向的改變不是連續漸變的，因此當居民從星球上的一個面移動到另一個面時，就必須要花費一些能量來改變重力的方向。我們可以用編號為1到30的30個整數來表達這個星球上任意兩個相鄰面之間重力改變需要花費的成本，其中每一個編號分別對應兩個面之間的一條邊如下圖所示，例如我們要從 11 號面移動到 12 號面就需要花費第30個整數所代表的成本。所有成本都是雙向的。

有一天，AC超人打算去拜訪他的朋友，他們兩人住在這顆星球的不同面上。給定 AC 超人和他的朋友居住在超能星球的哪一個面，以及跨越每一條邊所需要花費的能量成本，請幫忙計算 AC 超人最少需要花費多少成本才能與他的朋友見面。
輸入格式 第一列有兩個整數S、T (1 ≤ S, T ≤ 12 )，代表AC超人和他的朋友住在星球的哪一個面上。面的編號順序如題目圖片所示。接下來有 6 列，每一列有 5 個整數Ci (1 ≤ Ci ≤ 106，1 ≤ i ≤ 30 )，依序代表跨越第1, 2, 3 …, 30 號邊所需要花費的能量成本。邊的編號順序如題目圖片所示。
輸出格式
請輸出一個整數，代表最少需要花費的能量成本。
輸入範例1
2 12
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
輸出範例1
2
輸入範例2
1 12
1 999 999 999 999
1 2 3 4 999
999 999 999 999 999
999 999 999 3 999
3 5 999 4 1
999 999 2 999 999
輸出範例2
29
輸入範例1的說明：一條最短的路徑可能是2 → 8 → 12，花費成本2。
輸入範例2的說明：成本最少的路徑是1 → 2 → 3 → 4 → 5 → 6 → 10 → 11 → 7 → 8 → 9 → 12。
評分說明 此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，
各組詳細限制如下。
第一組（10分）：S = 1，且所有的C = 1。
第二組（30分）：所有的C = 1。 第三組（60分）：無特別限制。
附件: 您需要登錄才可以下載或查看附件。沒有帳號？註冊
收藏 分享
May

Rank: 9Rank: 9Rank: 9
2#
may發表於 2025-1-31 16:46 | 只看該作者

空間概念

在這個問題中，我們可以用圖的結構來表示面和邊之間的關係。超能星球總共有12個面，所以我們會有12個節點(vertex)；題目也已經提到總共會有30條邊連接這12個節點，每個節點會有5條邊。問題是這30條邊分別是連接哪兩個面(節點)呢？這就需要一點空間概念來幫助我們建圖了。

圖上明顯看得出來的是1號邊會連接第1、2個面；2號邊會連接第1、3個面…5號邊會連接第1、6個面。而6~10號邊也很容易觀察，6號邊是連接第2、3個面；7號邊是連接第3、4個面。
比較難想像的部分是第11~20號邊，這邊可以直接參考下圖。有了這些關係以後，我們可以建立一個陣列來幫助我們把第1~30個數值轉換成圖
附件: 您需要登錄才可以下載或查看附件。沒有帳號？註冊
May

TOP

Rank: 9Rank: 9Rank: 9
3#
may發表於 2025-1-31 16:47 | 只看該作者
  1. #include<bits/stdc++.h>
  2. //#include<iostream>
  3. //#include<vector>
  4. //#include<utility>
  5. //#include<algorithm>
  6. //#include<climits>
  7. using namespace std;

  9. int main()
  10. {
  11.     int S, T;
  12.     cin >> S >> T;
  13.     --S;
  14.     --T;
  15.     vector<vector<pair<int,int>>> graph(12);
  16.     constexpr int edges[30][2] =
  17.     {0, 1, 0, 2, 0, 3, 0, 4, 0, 5, //1-5
  18.      1, 2, 2, 3, 3, 4, 4, 5, 5, 1, //6-10
  19.      1, 8, 1, 7, 2, 7, 2, 6, 3, 6, //11-15
  20.      3, 10, 4, 10, 4, 9, 5, 9, 5, 8, //16-20
  21.       6, 7, 7, 8, 8, 9, 9, 10, 10, 6, //21-25
  22.       11, 6, 11, 7, 11, 8, 11, 9, 11, 10 //26-30
  23.      };
  24.     for(int i=0; i<30; ++i)
  25.     {
  26.         int cost;
  27.         cin >> cost;
  28.         graph[edges[i][0]].push_back({edges[i][1], cost});
  29.         graph[edges[i][1]].push_back({edges[i][0], cost});
  30.     }
  31.     vector<int> dist(12, INT_MAX);
  32.     vector<bool> visited(12, false);
  33.     dist[S] = 0;
  34.     while(!visited[T])
  35.     {
  36.         int min_dist = INT_MAX;
  37.         int min_node = 0;
  38.         for(int i=0; i<12; ++i)
  39.         {
  40.             if(!visited[i] && dist[i]<min_dist)
  41.             {
  42.                 min_node = i;
  43.                 min_dist = dist[i];
  44.             }
  45.         }
  46.         visited[min_node] = true;
  47.         for(auto &p: graph[min_node])
  48.         {
  49.             dist[p.first] = min(dist[p.first], dist[min_node]+p.second);
  50.         }
  51.     }
  52.     cout << dist[T] << endl;
  53. }
  54. /*
  55. 輸入範例1
  56. 2 12
  57. 1 1 1 1 1
  58. 1 1 1 1 1
  59. 1 1 1 1 1
  60. 1 1 1 1 1
  61. 1 1 1 1 1
  62. 1 1 1 1 1
  63. 輸出範例1
  64. 2
  65. 輸入範例2
  66. 1 12
  67. 1 999 999 999 999
  68. 1 2 3 4 999
  69. 999 999 999 999 999
  70. 999 999 999 3 999
  71. 3 5 999 4 1
  72. 999 999 2 999 999
  73. 輸出範例2
  74. 29
  75. */
複製代碼
May

TOP

返回列表