poj1724 ROADS

题意：

N个城市，编号1到N。城市间有R条单向道路。
每条道路连接两个城市，有长度和过路费两个属性。
Bob只有K块钱，他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N，输出-1
2<=N<=100
0<=K<=10000
1<=R<=10000
每条路的长度 L, 1 <= L <= 100
每条路的过路费T , 0 <= T <= 100

思路：

用d[i][j]表示从源点走到城市i并且花费为j的时候经过的最短距离。若在后续的搜索中，再次走到i时，如果总路费恰好为j，且此时的路径长度已经超过 d[i][j],则不必再走下去了。

1.深搜+剪枝

2.spfa+剪枝

实现：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <vector>

 #include <cstring>

 using namespace std;

 const int MAXN = ;

 const int MAXK = ;

 const int INF = 0x3f3f3f3f;

 struct node

 {

     int to, len, toll;

 };

 vector<node> G[MAXN + ];

 int k, n, m, s, t, l, T, minLen = INF;

 bool vis[MAXN + ];

 int d[MAXN + ][MAXK + ];

 void dfs(int now, int rem, int len)

 {

     if (now == n)

     {

         minLen = min(minLen, len);

         return;

     }

     for (int i = G[now].size() - ; i >= ; i--)

     {

         if (!vis[G[now][i].to] && rem >= G[now][i].toll)

         {

             if (d[G[now][i].to][rem - G[now][i].toll] <=

                 len + G[now][i].len || len + G[now][i].len >= minLen)

                 continue;

             d[G[now][i].to][rem - G[now][i].toll] = len + G[now][i].len;

             dfs(G[now][i].to, rem - G[now][i].toll, len + G[now][i].len);

             vis[G[now][i].to] = false;

         }

     }

 }

 int main()

 {

     cin >> k >> n >> m;

     for (int i = ; i < m; i++)

     {

         cin >> s >> t >> l >> T;

         node tmp;

         tmp.to = t;

         tmp.len = l;

         tmp.toll = T;

         if (s != t)

             G[s].push_back(tmp);

     }

     memset(d, 0x3f, sizeof(d));

     vis[] = true;

     dfs(, k, );

     if (minLen == INF)

         puts("-1");

     else

         cout << minLen << endl;

     return ;

 }

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <vector>

 #include <cstring>

 #include <queue>

 #include <functional>

 using namespace std;

 const int MAXN = ;

 const int MAXK = ;

 const int INF = 0x3f3f3f3f;

 struct node

 {

     int to, len, toll;

 };

 vector<node> G[MAXN + ];

 int k, n, m, s, t, l, T;

 struct co

 {

     int now, cost;

 };

 int d[MAXN + ][MAXK + ];

 int in[MAXN + ][MAXK + ];

 int spfa()

 {

     queue<co> q;

     co start;

     start.now = ;

     start.cost = ;

     q.push(start);

     in[][] = true;

     priority_queue<int, vector<int>, greater<int> > pq;

     pq.push(INF);

     while (!q.empty())

     {

         co tmp = q.front();

         q.pop();

         int now = tmp.now;

         int cost = tmp.cost;

         if (now == n)

         {

             pq.push(d[n][cost]);

         }

         in[now][cost] = false;

         for (int i = ; i < G[now].size(); i++)

         {

             if (cost + G[now][i].toll <= k &&

                 d[now][cost] + G[now][i].len < d[G[now][i].to][cost + G[now][i].toll])

             {

                 d[G[now][i].to][cost + G[now][i].toll] = d[now][cost] + G[now][i].len;

                 if (d[G[now][i].to][cost + G[now][i].toll] >= pq.top())

                     continue;

                 if (!in[G[now][i].to][cost + G[now][i].toll])

                 {

                     in[G[now][i].to][cost + G[now][i].toll] = true;

                     co son;

                     son.now = G[now][i].to;

                     son.cost = cost + G[tmp.now][i].toll;

                     q.push(son);

                 }

             }

         }

     }

     int minL = INF;

     for (int i = ; i <= k; i++)

     {

         minL = min(minL, d[n][i]);

     }

     return minL;

 }

 int main()

 {

     cin >> k >> n >> m;

     for (int i = ; i < m; i++)

     {

         cin >> s >> t >> l >> T;

         node tmp;

         tmp.to = t;

         tmp.len = l;

         tmp.toll = T;

         if (s != t)

             G[s].push_back(tmp);

     }

     memset(d, 0x3f, sizeof(d));

     for (int i = ; i <= k; i++)

     {

         d[][i] = ;

     }

     int minLen = spfa();

     if (minLen >= INF)

         puts("-1");

     else

         cout << minLen << endl;

     return ;

 }

最优性剪枝总结：

1. 从初始状态到当前状态的代价已经不小于目前找到的最优解，则剪枝。

2. 预测一下从当前状态到解的状态至少要花的代价W，如果W加上到达当前状态时已经花费的代价，必然不小于目前找到的最优解,则剪枝。

3. 如果到达某个状态A时，发现前面曾经也到达过A，且前面那次到达A所花代价更少，则剪枝。这要求记录到目前为止到达状态A时所能取得的最小代价。

巴特西

poj1724 ROADS

最新文章

热门文章