[討論] UVA 11367 Full tank 一直TLE

作者: darrenlee1 (darrenleeleelee)   2020-04-28 23:58:04
目前測資看起來是都沒有問題(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
作者: nevak (^o^)   2020-04-29 01:52:00
dfs先把路線走出來再回頭算最省錢的加油法會不會比較好呢

Links booklink

Contact Us: admin [ a t ] ucptt.com