開始用FLOY求最短路徑，奈何最后個測試點超時，只能再試試DIJ來求，然后過了 需要注意的地方： 首先加油站離最近房子的距離盡可能遠，如果有不同解，選路徑和最小的那個，還一樣選序號最小的一個，當然加油站里所有房子的最小路徑都不能超過給的數，代碼中貼有FLOY解法和DIJ解法，當然FLOY是超時的
#include<iostream>#include<vector>#include<string>#define INF 0x3f3f3fusing namespace std;int N, M, K, D;bool flag;int add, v;int change_index(string str){ if (str[0] == 'G') return N-1+stoi(string(str, 1)); else return stoi(str) - 1;}string change_name(int i){ if (i < N) return to_string(i+1); else return string("G") + to_string(i + 1 - N);}vector<vector<int>> arc;vector<int> Dis;vector<int> Tem;vector<bool> visited;bool DIJ(int index){ int num = 0; visited[index] = true; Dis[index] = 0; for (int t = 0;t < M + N;t++) if (arc[index][t] != INF) Tem[t] = arc[index][t]; while (num != N) { int temp_min=INF,temp_v; for (int t = 0;t < M + N;t++) if (!visited[t] && Tem[t] < temp_min) { temp_min = Tem[t];temp_v = t; } Dis[temp_v] = temp_min; visited[temp_v] = true; if (temp_v < N) { num++; add +=temp_min; if (temp_min < v) v = temp_min; if (temp_min > D) { flag = false;break; } } for (int t = 0;t < M + N;t++) if (!visited[t] && Tem[t]>temp_min + arc[temp_v][t]) Tem[t] = temp_min + arc[temp_v][t]; } return true;}int main(){ cin >> N >> M >> K >> D; if (N == 0) {新聞熱點
疑難解答
