【堆优化Dijkstra+字典序最短路方案】HDU1385-Minimum Transport Cost

【题目大意】

给出邻接矩阵以及到达各个点需要付出的代价（起点和终点没有代价），求出从给定起点到终点的最短路，并输出字典序最小的方案。

【思路】

在堆优化Dijkstra中，用pre记录前驱。如果新方案和旧方案相等，比较两个方案的字典序。

【坑点】

我先求出了最短路（包括终点要付出代价），输出的时候再减去终点的代价。

有可能会给出S==T的情况……在这种情况下，最短路就是0，减去代价要变成负数了QAQ所以要特判一下。坑了好几个小时orz

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<cstdlib>
 #include<cmath>
 #include<queue>
 #include<vector>
 using namespace std;
 const int MAXN=+;
 const int INF=0x7fffffff;

 struct edge
 {
     int to,len;
 };

 vector<edge> E[MAXN];
 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pque;
 int vis[MAXN],dis[MAXN],pre[MAXN],tax[MAXN];
 int s1[MAXN],s2[MAXN],n;

 void addedge(int u,int v,int w)
 {
     E[u].push_back((edge){v,w});
 }

 void init()
 {
     for (int i=;i<MAXN;i++) vector<edge>().swap(E[i]);
     while (!pque.empty()) pque.pop();
     for (int i=;i<=n;i++)
         for (int j=;j<=n;j++)
         {
             int aij;
             scanf("%d",&aij);
             if (aij>= && i!=j) addedge(i,j,aij);
         }
     for (int i=;i<=n;i++) scanf("%d",&tax[i]);
 }

 int compare(int now,int before)
 {
     memset(s1,,sizeof(s1));
     memset(s2,,sizeof(s2));
     int i=,j=-;
     s1[]=before;
     while (now!=) s1[++i]=now,now=pre[now];
     while (before!=) s2[++j]=before,before=pre[before];
     for (;i>= && j>=;i--,j--)
         if (s1[i]<s2[j]) return ;
             else if (s1[i]>s2[j]) return ;
     return (s1<s2);
 }

 int dijkstra(int S,int T)
 {
     for (int i=;i<=n;i++) vis[i]=,dis[i]=INF,pre[i]=-;
     dis[S]=,pre[S]=;
     pque.push(pair<int,int>(,S));
     while (!pque.empty())
     {
         int u=pque.top().second;pque.pop();
         vis[u]=;
         for (int i=;i<E[u].size();i++)
         {
             int v=E[u][i].to,len=E[u][i].len+tax[v];
             if (dis[v]>=dis[u]+len)
             {
                 if (dis[v]>dis[u]+len)
                 {
                     dis[v]=dis[u]+len;
                     pre[v]=u;
                     pque.push(pair<int,int>(dis[v],v));
                 }
                 else if (dis[v]==dis[u]+len && compare(u,v))
                 {
                     pre[v]=u;
                     pque.push(pair<int,int>(dis[v],v));
                 }
             }
         }
     }

     int i=,now=T;
     while (now!=) s1[++i]=now,now=pre[now];
     printf("From %d to %d :\n",S,T);
     printf("Path: ");
     while (i>=)
     {
         printf("%d",s1[i--]);
         if (i!=) printf("-->");
     }
     printf("\nTotal cost : %d\n\n",(S==T)?:dis[T]-tax[T]);
     //注意如果S==T的时候，就不要减去tax了，否则会出现负值。
 }

 void solve()
 {
     int a,b;
     while (scanf("%d%d",&a,&b))
     {
         if (a==- && a==b) return;
         dijkstra(a,b);
     }
 }

 int main()
 {
     while (scanf("%d",&n))
     {
         if (n==) break;
         init();
         solve();
     }
     return ;
 }

附上随机数据生成：

 #include<bits/stdc++.h>
 using namespace std;

 int main()
 {
     freopen("samplein.txt", "w", stdout);
    srand((unsigned)time(NULL));
     int n=rand() % ;
     int ne;
     cout<<n<<endl;
     for (int i=;i<n;i++)
     {
         for (int j=;j<n;j++)
         {
             if (i==j)
             {
                 printf("%d",);
             }
             else
             {
                 if((rand()%n)<(n/))
                 {
                     printf("-1");
                 }
                 else
                 {
                     printf("%d",(rand()%(n-)+));
                 }
             }
             printf(" ");
         }
         printf("\n");

     }

     for (int i=;i<n;i++)
     {
         printf("%d ",(rand()%n));
     } 

     printf("\n");
     int tmp=rand()%n;
     for (int i=;i<tmp;i++)
     {
         int temp1=(rand()%(n-)+);
         int temp2=(rand()%(n-)+);
         printf("%d %d\n",temp1,temp2);

     } 

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

     fclose(stdout);
     return ;
 }