POJ 3411 Paid Roads(SPFA || DFS)

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

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

二维SPFA

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 #include <iostream>

 using namespace std ;

 struct node

 {

     int uu ;

     int p,r ;

     bool vis ;

 } mapp[][];

 int N,m ;

 int dis[][] ;

 int cost ;

 bool vist[] ;

 const int INF =  ;

 int spfa()

 {

     queue<pair<int,int> >Q ;

     Q.push(make_pair(,)) ;

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

         for(int j =  ; j <  ; j++)

             dis[i][j] = INF ;

     memset(vist,false ,sizeof(vist)) ;

     dis[][] =  ;

     while(!Q.empty())

     {

         int a = Q.front().first ;

         int b = Q.front().second ;

         Q.pop() ;

         vist[a] = false ;

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

         {

             if(mapp[a][i].vis)

             {

                 if( b & ( << (mapp[a][i].uu-))) cost = mapp[a][i].p ;//減一是為了讓狀態從1開始，1，2，4....

                 else cost = mapp[a][i].r ;

                 if(dis[i][b | ( << (mapp[a][i].uu-))] > cost + dis[a][b])

                 {

                     dis[i][b | ( << (mapp[a][i].uu-))] = cost + dis[a][b] ;

                     if(!vist[i])

                     {

                         vist[i] = true ;

                         Q.push(make_pair(i,b | ( << (mapp[a][i].uu-)))) ;

                     }

                 }

             }

         }

     }

     int minn = INF ;

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

         minn = min(minn,dis[N][i]) ;

     return minn ;

 }

 int main()

 {

     int u,v,uu,p,r ;

     while(~scanf("%d %d",&N,&m))

     {

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

         {

             scanf("%d %d %d %d %d",&u,&v,&uu,&p,&r) ;

             mapp[u][v].vis = true ;

             mapp[u][v].uu = uu ;

             mapp[u][v].p = p ;

             mapp[u][v].r = r ;

         }

         int ans = spfa() ;

         if(ans < INF)

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

         else printf("impossible\n") ;

     }

     return  ;

 }

DFS

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #define oo 9999999

 using namespace std ;

 int N,M ;

 struct node

 {

     int u,v,w ;

     int P,R ;

 } road[];

 int vis[] ,ans;

 void dfs(int u,int cost)

 {

     if(u == N && ans > cost)

     {

         ans = cost ;

         return ;

     }

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

     {

         if(u == road[i].u && vis[road[i].v] <= )

         {

             vis[road[i].v] ++ ;

             if(vis[road[i].w])

                 dfs(road[i].v,cost+road[i].P) ;

             else dfs(road[i].v,cost+road[i].R) ;

             vis[road[i].v] -- ;

         }

     }

 }

 int main()

 {

     while(~scanf("%d %d",&N,&M))

     {

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

             scanf("%d %d %d %d %d",&road[i].u,&road[i].v,&road[i].w,&road[i].P,&road[i].R) ;

         memset(vis,,sizeof(vis)) ;

         vis[] =  ;

         ans = oo ;

         dfs(,) ;

         if(ans == oo)

             printf("impossible\n") ;

         else

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

     }

     return  ;

 }

巴特西

POJ 3411 Paid Roads(SPFA || DFS)

最新文章

热门文章