POJ 3411 Paid Roads(SPFA || DFS)

题意：要从1城市到n城市，求最短路是多少，从a城市到达b城市的路程，如果你到过c城市，则需要走p，否则走r长。

思路：因为可以来回走，所以不能用单纯的最短路，可以用二维SPFA，状态压缩一下，第二维来记录状态，表示到过这个点的第几个状态。也可以用DFS，因为最多十个点，所以如果走某一个点走过三遍说明就是真的只增加费用了，也就是真正的在走环路了。DFS分析

二维SPFA

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 struct node
 9 {
10     int uu ;
11     int p,r ;
12     bool vis ;
13 } mapp[12][12];
14 
15 int N,m ;
16 int dis[12][1025] ;
17 int cost ;
18 bool vist[12] ;
19 const int INF = 9999999 ;
20 
21 int spfa()
22 {
23     queue<pair<int,int> >Q ;
24     Q.push(make_pair(1,1)) ;
25     for(int i = 1 ; i < 12 ; i++)
26         for(int j = 1 ; j < 1025 ; j++)
27             dis[i][j] = INF ;
28     memset(vist,false ,sizeof(vist)) ;
29     dis[1][1] = 0 ;
30     while(!Q.empty())
31     {
32         int a = Q.front().first ;
33         int b = Q.front().second ;
34         Q.pop() ;
35         vist[a] = false ;
36         for(int i = 1 ; i <= N ; i++)
37         {
38             if(mapp[a][i].vis)
39             {
40                 if( b & (1 << (mapp[a][i].uu-1))) cost = mapp[a][i].p ;//減一是為了讓狀態從1開始，1，2，4....
41                 else cost = mapp[a][i].r ;
42                 if(dis[i][b | (1 << (mapp[a][i].uu-1))] > cost + dis[a][b])
43                 {
44                     dis[i][b | (1 << (mapp[a][i].uu-1))] = cost + dis[a][b] ;
45                     if(!vist[i])
46                     {
47                         vist[i] = true ;
48                         Q.push(make_pair(i,b | (1 << (mapp[a][i].uu-1)))) ;
49                     }
50                 }
51             }
52         }
53     }
54     int minn = INF ;
55     for(int i = 1 ; i < 1 << N  ; i++)
56         minn = min(minn,dis[N][i]) ;
57     return minn ;
58 }
59 int main()
60 {
61     int u,v,uu,p,r ;
62     while(~scanf("%d %d",&N,&m))
63     {
64         for(int i = 1 ; i <= m ; i++)
65         {
66             scanf("%d %d %d %d %d",&u,&v,&uu,&p,&r) ;
67             mapp[u][v].vis = true ;
68             mapp[u][v].uu = uu ;
69             mapp[u][v].p = p ;
70             mapp[u][v].r = r ;
71         }
72         int ans = spfa() ;
73         if(ans < INF)
74             printf("%d
",ans) ;
75         else printf("impossible
") ;
76     }
77     return 0 ;
78 }

View Code

DFS

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #define oo 9999999
 5 using namespace std ;
 6 
 7 int N,M ;
 8 struct node
 9 {
10     int u,v,w ;
11     int P,R ;
12 } road[12];
13 int vis[12] ,ans;
14 
15 void dfs(int u,int cost)
16 {
17     if(u == N && ans > cost)
18     {
19         ans = cost ;
20         return ;
21     }
22     for(int i = 0 ; i < M ; i++)
23     {
24         if(u == road[i].u && vis[road[i].v] <= 3)
25         {
26             vis[road[i].v] ++ ;
27             if(vis[road[i].w])
28                 dfs(road[i].v,cost+road[i].P) ;
29             else dfs(road[i].v,cost+road[i].R) ;
30             vis[road[i].v] -- ;
31         }
32     }
33 }
34 int main()
35 {
36     while(~scanf("%d %d",&N,&M))
37     {
38         for(int i = 0 ; i < M ; i++)
39             scanf("%d %d %d %d %d",&road[i].u,&road[i].v,&road[i].w,&road[i].P,&road[i].R) ;
40         memset(vis,0,sizeof(vis)) ;
41         vis[1] = 1 ;
42         ans = oo ;
43         dfs(1,0) ;
44         if(ans == oo)
45             printf("impossible
") ;
46         else
47             printf("%d
",ans) ;
48     }
49     return 0 ;
50 }

View Code