ccf 201712-4 行车路线(70分)

ccf 201712-4 行车路线

解题思路：

　　首先Dijkstra是基于贪心算法的，即每一次作出的选择都具有贪心选择性。此题由于有“如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s的疲劳度。”这种情况，所以不能使用Dijkstra算法。

　　这里使用Bellman-Ford算法

70分备份待修改：

 #include<iostream>

 #include<cstring>

 using namespace std;

 int n,m;//n为路口的数量，m为道路的数量

 const int maxn =  + ;

 const int maxm =  + ;

 const int INF = ;//无穷大

 struct node{

     int ci,cj;

     int type;

     int cij;

 }path[*maxm];

 int Edge[maxn][maxn];//记录两个点之间路径的编号

 int dist[maxn];//记录源点1到每一个节点的最短路

 int pro[maxn];//记录每一个节点的前驱结点

 void bellman()

 {

     memset(dist,INF,sizeof(dist));

     dist[] = ;

     memset(pro,-,sizeof(pro));

     pro[] = ;//1没有前驱

     for(int k=;k<n;k++)///进行n-1次松弛操作

     {

         bool flag = false;

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

         {

             if(path[i].type == )//大道

             {

                 if(dist[path[i].cj] > dist[path[i].ci]+path[i].cij)

                 {

                     dist[path[i].cj] = dist[path[i].ci]+path[i].cij;

                     pro[path[i].cj] = path[i].ci;

                     flag = true;

                 }

              } else{//小道

              //首先要计算出连续走小路多长时间

                 int con = path[i].cij;

                 int temp = i;

                  if(pro[path[i].ci] != - && pro[path[i].ci] != )//已经加入,有前驱

                  {

                      int pathnum = Edge[pro[path[temp].ci]][path[temp].ci];

                      while( path[pathnum].type == )//连续走小道

                      {

                          con += path[pathnum].cij;

                          temp = Edge[pro[path[temp].ci]][path[temp].ci];

                          if(pro[path[pathnum].ci] == ) break;//到达起始结点

                          pathnum = Edge[pro[path[temp].ci]][path[temp].ci];

                       }

                   }

                  if(dist[path[i].cj]>dist[path[temp].ci] + con*con)

                  {

                      dist[path[i].cj]=dist[path[temp].ci] + con*con;

                      pro[path[i].cj] = path[i].ci;

                     flag = true;

                  }

              }

         }

         if(!flag) break;

      }

 }

 int main()

 {

     while(cin>>n>>m)

     {

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

         {

             cin>>path[i].type>>path[i].ci>>path[i].cj>>path[i].cij;

             i++;

             path[i].ci = path[i-].cj;path[i].cj = path[i-].ci;

             path[i].cij = path[i-].cij;path[i].type = path[i-].type;

             Edge[path[i].ci][path[i].cj] = i;

             Edge[path[i].cj][path[i].ci] = i-;

         }

         bellman();

         cout<<dist[n]<<endl;

     }

     return ;

  }