目前測資看起來是都沒有問題(udebug也過)，把cin都改成scanf，不知道還有哪邊可以優化，一直TLE，想請各位幫忙看一下。 #include <bits/stdc++.h> using namespace std; const int maxn = 1000+10; int n, m, u, v, d, c, s, e, Q; int cost[maxn]; int weight[maxn][maxn]; vector<int> adj[maxn]; int dp[maxn][100+10]; struct Car { int cur, left, costSum; bool operator<(const Car &other)const{ return costSum > other.costSum; } }; int dij() { if(s == e) return 0; for(int i = 0; i < n; i++) for(int j = 0; j <= c; j++) dp[i][j] = 1e9; priority_queue<Car> pq; pq.push(Car{s, 0, 0}); while(!pq.empty()){ auto top = pq.top(); pq.pop(); if(dp[top.cur][top.left] < top.costSum) continue; if(top.cur == e && top.left == 0) return dp[top.cur][top.left]; for(auto i : adj[top.cur]){ if(c < weight[top.cur][i]) continue; for(int j = top.left; j <= c; j++){ if(j < weight[top.cur][i]) continue; int OilCost = cost[top.cur] * (j - top.left); int temp = j - weight[top.cur][i]; if(dp[i][temp] > top.costSum + OilCost){ dp[i][temp] = top.costSum + OilCost; } pq.push(Car{i, j - weight[top.cur][i], top.costSum + OilCost}); } } } return 1e9; } int main(int argc, char const *argv[]) { while(scanf("%d%d", &n, &m) != EOF){ for(int i = 0; i < n; i++){ adj[i].clear(); scanf("%d", &cost[i]); } for(int i = 0; i < m; i++){ scanf("%d%d%d", &u, &v, &d); adj[u].push_back(v); adj[v].push_back(u); weight[u][v] = d; weight[v][u] = d; } scanf("%d", &Q); while(Q--){ scanf("%d%d%d", &c, &s, &e); int res = dij(); if(res == 1e9) printf("impossible\n"); else printf("%d\n", res); } } return 0; } 題目在這邊 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2352&mosmsg=Submission+received+with+ID+24949480 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.141.67.113 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1588089488.A.85E.html