HDU 1385Minimum Transport Cost 最短路输出路径

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1385

题意

给定n个城镇，从s到t运货需要路费，路径中除了s和t之外，经过每个城镇还要额外收税。求s到t的最小花费，并输出字典序最小的路径

思路

一开始从s到t正向跑dj，发现倒着走反而才是字典序最小的，要输出从s->t的最短路且字典序最小，从t倒着走到s，每次拿编号最小的点去松弛其他点。因为s和t不计算税收，所以需先将s的税暂时赋0

#include<cstdio>
#include<queue>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<string>
#include<set>
#include<stack>
#include<algorithm>
#define cle(a) memset(a,0,sizeof(a))
#define inf(a) memset(a,0x3f,sizeof(a))
#define ll long long
#define Rep(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
#define INF2 9223372036854775807ll
const int INF = ( 2e9 ) + 2;
const ll maxn = 1e4+10;
int mp[maxn][maxn];
int p[maxn],d[maxn],vis[maxn],pre[maxn];
int n;
void dijkstra(int s,int t)
{
for(int i=1; i<=n; i++)d[i]=INF;
    d[t]=0;
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
for(int i=1; i<=n; i++)
    {
int u=-1,mn=INF;
for(int j=n; j>=1; j--)
if(!vis[j]&&d[j]<mn)
                mn=d[u=j];
if(u==-1)break;
        vis[u]=1;
for(int v=n; v>=1; v--)
if(mp[v][u]!=-1&&u!=v)
            {
if(d[v]>d[u]+mp[v][u]+p[v])
                {
                    d[v]=d[u]+mp[v][u]+p[v];
                    pre[v]=u;
                }
else if(d[v]==d[u]+mp[v][u]+p[v])
                {
                    pre[v]=min(pre[v],u);
                }

            }
    }
printf("From %d to %d :\n",s,t);
printf("Path: ");
for(int i=s; i!=-1; i=pre[i])
if(i==s)
printf("%d",i);
else
printf("-->%d",i);
printf("\nTotal cost : %d\n",d[s]);
}
int main()
{
// freopen("in.txt","r",stdin);
while(~scanf("%d",&n)&&n)
    {
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&mp[i][j]);
for(int i=1; i<=n; i++)
scanf("%d",&p[i]);
int u,v;
        u=v=0;
while(1)
        {
scanf("%d%d",&u,&v);
if(u==-1&&v==-1)break;
int temp=p[u];
            p[u]=0;
            dijkstra(u,v);
printf("\n");
            p[u]=temp;
        }
    }
}