hdu Minimum Transport Cost(按字典序输出路径)
2014-05-16 11:31:27         来源：hdu Minimum Transport Cost(按字典序输出路径)

spfa：拿一个pre[]记录前驱，不同的是在松弛的时候，要考虑和当前点的dis值相等的情况，解决的办法是dfs找出两条路径中字典序较小的，pre[]去更新。把路径当做字符串处理。

#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;

int n;
int tax[maxn];
int Map[maxn][maxn];
int dis[maxn],inque[maxn];
int pre[maxn];
int pos = 0;

void dfs(int u, char *s)
{
if(u == -1)
return;
dfs(pre[u],s);
s[pos++] = u+'0';
}

bool solve(int v, int u)
{
char s1[maxn],s2[maxn];

//寻找先前的路径
pos = 0;
dfs(v,s1);
s1[pos] = '';
//寻找由u更新的路径
pos = 0;
dfs(u,s2);
s2[pos++] = v+'0';
s2[pos] = '';

if(strcmp(s1,s2) > 0) return true;
return false;

}

int spfa(int s, int t)
{
queue  que;
memset(dis,INF,sizeof(dis));
memset(inque,0,sizeof(inque));
memset(pre,-1,sizeof(pre));

dis[s] = 0;
inque[s] = 1;
que.push(s);

while(!que.empty())
{
int u = que.front();
que.pop();
inque[u] = 0;

for(int v = 1; v <= n; v++)
{
if(Map[u][v] > 0)
{
int tmp = dis[u] + Map[u][v] + tax[v];

if(tmp < dis[v])//直接更新
{
dis[v] = tmp;
pre[v] = u;
if(!inque[v])
{
inque[v] = 1;
que.push(v);
}
}
else if(tmp == dis[v] && solve(v,u))
{
pre[v] = u;
}

}
}
}

return dis[t];
}

void output(int s, int t)
{
int res[maxn];
int cnt = 0;
int tmp = t;

while(pre[tmp] != -1)
{
res[cnt++] = tmp;
tmp = pre[tmp];
}
res[cnt] = s;
printf(Path: );
for(int i = cnt; i >= 1; i--)
printf(%d-->,res[i]);
printf(%d
,res[0]);
}

int main()
{
while(~scanf(%d,&n) && n)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
scanf(%d,&Map[i][j]);
}
for(int i = 1; i <= n; i++)
scanf(%d,&tax[i]);
int u,v;
while(~scanf(%d %d,&u,&v))
{
if(u == -1 && v == -1) break;
int tmp1 = tax[u];//备份
int tmp2 = tax[v];

tax[u] = 0;
tax[v] = 0;

printf(From %d to %d :
,u,v);
int ans = spfa(u,v);
output(u,v);
printf(Total cost : %d

,ans);
//恢复备份
tax[u] = tmp1;
tax[v] = tmp2;

}
}
return 0;
}

floyd:pre[i][j]记录i到j路径上距离i最近的点，输出路径时按pre正向输出。感觉floyd很强大啊，还可以这样记录路径。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define _LL __int64
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn =  110;
int Map[maxn][maxn];
int tax[maxn];
int pre[maxn][maxn];
int n;

void floyd()
{
//初始化
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
pre[i][j] = j;

for(int k = 1; k <= n; k++)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(Map[i][k] > 0 && Map[k][j] > 0)
{
int tmp = Map[i][k] + Map[k][j] + tax[k];

if(tmp < Map[i][j]) //小于直接更新
{
Map[i][j] = tmp;
pre[i][j] = pre[i][k];
}
else if(tmp == Map[i][j])
{
pre[i][j] = min(pre[i][k],pre[i][j]);
}
}
}
}
}
}

void output(int s, int t)
{
printf(Path: );
int tmp = s;
while(tmp != t)
{
printf(%d-->,tmp);
tmp = pre[tmp][t];
}
printf(%d
,t);

}

int main()
{
while(~scanf(%d,&n) && n)
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
scanf(%d,&Map[i][j]);
if(Map[i][j] == -1)
Map[i][j] = INF;
}

for(int i = 1; i <= n; i++)
scanf(%d,&tax[i]);

int u,v;
floyd();
while(~scanf(%d %d,&u,&v))
{
if(u == -1 && v == -1) break;
printf(From %d to %d :
,u,v);
output(u,v);
printf(Total cost : %d

,Map[u][v]);
}
}
return 0;
}