广大暑假训练1 E题 Paid Roads(poj 3411) 解题报告

题目链接：http://poj.org/problem?id=3411

题目意思：N个city 由 m 条路连接，对于一条路（假设连接Cityia和 Cityb），如果从Citya 去 Cityb的途中，之前已经走过Cityc（可能会等于a），那么就可以交p的钱，否则之前未走过Cityc，就一定要交r 的路费啦。

注意，一个点可以被反复多次走，也就是可能构成环，虽然路走长了，但路费便宜了，这个问题要考虑到。还有就是剪枝啦：如果当前求得的路费比以前求得的答案要大，那就要回溯。

mincost 明明是全局变量，多手在main里又重新声明，搞了我1个多小时才发现 = =....

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int head[maxn];

 int point_vis[maxn];

 int N, m, mincost;

 struct adjlist   // 邻接表

 {

     int b, c, p, r;

     int next;

 }node[maxn];

 void dfs(int next, int cost)

 {

     if (point_vis[next] > N || cost >= mincost)   // 某一点被经过的次数多于N 或者当前cost比之前求出的minsum要大就回溯

         return;

     if (next == N)

     {

         mincost = cost;

         return;

     }

     for (int i = head[next]; i != -; i = node[i].next)

     {

         int v = node[i].b;

         point_vis[node[i].b]++;

         if (point_vis[node[i].c] >= )    // 之前这个中间点c有访问过，就可以交纳在点c的费用p

             dfs(node[i].b, cost+node[i].p);

         else      // 之前该点木有走过，只能乖乖交 r 这个费用了

             dfs(node[i].b, cost+node[i].r);

         point_vis[node[i].b]--;

     }

 }

 int main()

 {

     while (scanf("%d%d", &N, &m) != EOF)

     {

         int t1, cnt = ;

         memset(head, -, sizeof(head));

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

         {

             scanf("%d", &t1);

             node[cnt].next = head[t1];

             scanf("%d%d%d%d", &node[cnt].b, &node[cnt].c, &node[cnt].p, &node[cnt].r);

             head[t1] = cnt++;

         }

         memset(point_vis, , sizeof(point_vis));

         mincost = maxn;

         point_vis[]++;

         dfs(, );

         if (mincost == maxn)

             printf("impossible\n");

         else

             printf("%d\n", mincost);

     }

     return ;

 }

巴特西

广大暑假训练1 E题 Paid Roads(poj 3411) 解题报告

最新文章

热门文章