poj2679 Adventurous Driving 最短路

http://poj.org/problem?id=2679

写完这道题内心是崩溃的, 写个题解纪念一下

题意:

　　给你n个点m条边,起点是st,终点是end,给你一些边,这些边带有费用和长度,让你求从起点到终点的最小费用,并且在满足最小费用时满足最小长度.

　　输入(u,v,w1[len]w2) 表示u到v有一条费用为w1,长度为len的边;v到u有一条费用为w2,长度为len的有向边

说下大概思路

1.先删边,保留与这个点相连最小的边

　　具体实现:

　　　　if(first[st] != -1&&val > a[first[st]].w)return;

　　　　如果发现当前st所连接的上一条边的权值比当前插入边的权值小,就返回,不加入这条边

　　　　if(first[st] != -1&&val < a[first[st]].w)first[st] = -1;

　　　　那么反之,上一条边所连接的权值比当前插入的权值大,就把当期的first数组连向空节点,使得无法访问到权值的大边　　

2.spfa看起点能否到终点,不能到就输出VOID,能到 [并且无环] 直接输出最小费用和长度

3.然后处理有负环的情况 , 判断从st到end的路上是否有环 , 如果直接spfa只能判断这个图上是否有环,而不是st到end的路上是否有环

　　①首先我们知道cnt数组[记录一个点入队次数,当入队次数大于n说明由负环]

　　②如果这个点的cnt大于n说明st可以到这个节点,并且这个点在一个环中

　　③对②中的点进行bfs[或者dfs]如果这个点能到end就说明这个点在环上并且end也在环上,那么就可以输出UNBOUND

　　④如果以上皆不符合就输出最小费用和长度

PS:我就不用建反边的方法

  1 #include <stdio.h>
  2 #include <queue>
  3 #include <string.h>
  4 #define INF 100010
  5 #define maxn 50010
  6 #include <algorithm>
  7 using namespace std;
  8 int first[maxn], get[maxn], vis[maxn], cont[maxn], dis[maxn], le[maxn], flag;
  9 int n, m, st, end, tot, circle;
 10 struct node
 11 {
 12     int u, v, w, len, next;
 13 }a[maxn];
 14 void addedge(int st, int end, int val, int len)
 15 {
 16     if(first[st] != -1&&val > a[first[st]].w)return;
 17     if(first[st] != -1&&val < a[first[st]].w)first[st] = -1;
 18     a[++tot].u = st;a[tot].v=end;a[tot].w = val;a[tot].len = len;
 19     a[tot].next = first[st];first[st] = tot;
 20 }
 21 void bfs(int s)
 22 {
 23     queue<int > q;
 24     q.push(s);
 25     get[s] = 1;
 26     while(!q.empty())
 27     {
 28         int u = q.front();q.pop();
 29         for(int e = first[u]; e != -1; e = a[e].next)
 30         {
 31             int v = a[e].v;
 32             if(!get[v])
 33             {
 34                 get[v] = 1;
 35                 q.push(v);
 36             }
 37             if(v == end)
 38                 circle = 1;
 39         }
 40     }
 41 }
 42 int spfa()
 43 {
 44     queue<int > q;
 45     for(int i = 0; i <= n; i++)dis[i] = INF, vis[i] = 0;
 46     for(int i = 0; i <= n; i++)le[i] = INF;
 47     q.push(st);
 48     le[st] = 0;
 49     dis[st] = 0;
 50     vis[st] = 1;cont[st]++;
 51     while(!q.empty())
 52     {
 53         int u = q.front();q.pop();vis[u] = 0;
 54         for(int e = first[u]; e != -1; e = a[e].next)
 55         {
 56             int v = a[e].v;
 57             if(dis[u]+a[e].w < dis[v]||(dis[u]+a[e].w == dis[v]&&le[u]+a[e].len < le[v]))
 58             {
 59                 dis[v] = dis[u] + a[e].w;
 60                 le[v] = le[u] + a[e].len;
 61                 if(!vis[v])
 62                 {
 63                   q.push(v);
 64                   vis[v] = 1;
 65                   cont[v]++;
 66                  }
 67             }
 68             if(cont[v] > n+1)
 69             {
 70                 return 1;
 71             }
 72         }
 73     }
 74     return 0;
 75 }
 76 int main()
 77 {
 78     int x, y, w1, w2, len;
 79     while(~scanf("%d %d %d %d", &n, &m, &st, &end))
 80     {
 81         flag = 1;tot = 0;
 82         memset(first, -1, sizeof(first));
 83         memset(cont, 0, sizeof(cont));
 84         for(int i = 1; i <= m; i++)
 85         {
 86             scanf(" (%d,%d,%d[%d]%d)", &x, &y, &w1, &len, &w2);
 87             addedge(x, y, w1, len);addedge(y, x, w2, len);
 88         }
 89         flag = spfa();
 90         if(dis[end] == INF)
 91             printf("VOID
");
 92         else if(!flag){printf("%d %d
", dis[end], le[end]);continue;}
 93         else {
 94 
 95             for(int i = 0; i < n; i++)
 96             {
 97                 if(cont[i] > n){
 98                     memset(get, 0, sizeof(get));
 99                     circle = 0;
100                     bfs(i);
101                     if(circle)break;
102                 }
103             }
104             if(circle || cont[end] > n)
105                printf("UNBOUND
");
106             else printf("%d %d
", dis[end], le[end]);
107         }
108     }
109 }

View Code