/*
spfa
*/
#include
#include
#include
using namespace std;
#define inf 0x3fffffff
#define N 1100
int a[N][N];
int b[N];
int n;
int pre[N],dis[N],vis[N];
void init()
{
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
}
int Min(int v,int vv)
{
return v>vv?vv:v;
}
int len;
void dfs(int k,char s[])
{
if(k==-1)return ;
dfs(pre[k],s);
s[len++]=k+'0';
return ;
}
int cmp(int jnext,int now)
{
char sf[N],sn[N];
len=0;
dfs(jnext,sf);
sf[len]=0;
len=0;
dfs(now,sn);
sn[len++]=jnext+'0';
sn[len]=0;
if(strcmp(sf,sn)>0)
return 1;
return 0;
}
void spfa(int s,int t)
{
int i;
for(i=1; i<=n; i++)
dis[i]=inf;
dis[s]=0;
queueq;
q.push(s);
while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=0;
for(i=1; i<=n; i++)
{
if(dis[cur]==inf)continue;
if(a[cur][i]<0||i==cur)continue;
if(dis[i]>dis[cur]+a[cur][i]+b[i])
{
dis[i]=dis[cur]+a[cur][i]+b[i];
pre[i]=cur;
if(!vis[i])
{
vis[i]=1;
q.push(i);
}
}
else if(dis[i]==dis[cur]+a[cur][i]+b[i]&&cmp(i,cur))// cur
pre[i]=cur;
}
}
return ;
}
void print(int t)
{
if(pre[t]==-1)
{
printf("%d",t);
return ;
}
print(pre[t]);
printf("-->%d",t);
return ;
}
int main()
{
int i,s,j,t;
while(scanf("%d",&n),n)
{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
for(i=1; i<=n; i++)
scanf("%d",&b[i]);
while(scanf("%d%d",&s,&t),s!=-1&&t!=-1)
{
int sb=b[s],st=b[t];// 0
b[s]=0;//， dis[t]-b[t] ， wa
b[t]=0;//
init();
spfa(s,t);
printf("From %d to %d :
",s,t);
printf("Path: ");
print(t);
printf("
");
printf("Total cost : %d
",dis[t]);
b[s]=sb;//
b[t]=st;//
}
}
return 0;
}
/*
floyd
*/
#include
#include
#define N 550
#define inf 0x3fffffff
int dis[N][N],path[N][N];
int b[N];
int n;
void floyd()
{
int i,j,k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(dis[i][k]==inf||dis[k][j]==inf)continue;
int tmp=dis[i][k]+dis[k][j]+b[k];
if(dis[i][j]>tmp)
{
dis[i][j]=tmp;
path[i][j]=path[i][k];
}
else if(dis[i][j]==tmp&&path[i][j]>path[i][k]) //
path[i][j]=path[i][k];
}
return ;
}
int main()
{
int i,j,k;
while(scanf("%d",&n),n)
{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
scanf("%d",&dis[i][j]);
if(dis[i][j]==-1)dis[i][j]=inf;
path[i][j]=j;
}
for(i=1; i<=n; i++)
scanf("%d",&b[i]);
floyd();
int s,t;
while(scanf("%d%d",&s,&t),s!=-1&&t!=-1)
{
printf("From %d to %d :
",s,t);
printf("Path: ");
printf("%d",s);
k=s;
while(k!=t)
{
k=path[k][t];
printf("-->%d",k);
}
printf("
");
printf("Total cost : %d
",dis[s][t]);
}
}
return 0;
}
/*
dijkstar
*/
#include
#include
#define N 550
#define inf 0x3fffffff
int pre[N],dis[N],vis[N];
int a[N][N];
int b[N];
int n;
void init()
{
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
}
int len;
void dfs(int k,char s[])
{
if(k==-1) return ;
dfs(pre[k],s);
s[len++]=k+'0';
}
int cmp(int fir,int now)
{
char sf[N],sn[N];
len=0;
dfs(fir,sf);
sf[len]=0;
len=0;
dfs(now,sn);
sn[len++]=fir+'0';
sn[len]=0;
if(strcmp(sf,sn)>0)
return 1;
return 0;
}
void dijkstra(int s)
{
int i,j;
for(i=1; i<=n; i++)
{
if(i==s)continue;//
dis[i]=a[s][i]+b[i];//
if(a[s][i]dis[j]&&vis[j]==0)
{
minn=dis[j];
index=j;
}
vis[index]=1;
for(j=1; j<=n; j++)
if(vis[j]==0&&a[index][j]dis[index]+a[index][j]+b[j])
{
dis[j]=dis[index]+a[index][j]+b[j];
pre[j]=index;
}
else if(dis[j]==dis[index]+a[index][j]+b[j]&&cmp(j,index))// spfa
pre[j]=index;
}
}
return ;
}
void print(int k)
{
if(pre[k]==-1)
{
printf("%d",k);
return ;
}
print(pre[k]);
printf("-->%d",k);
}
int main()
{
int i,j;
while(scanf("%d",&n),n)
{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==-1)
a[i][j]=inf;
}
for(i=1; i<=n; i++)
scanf("%d",&b[i]);
int s,t;
while(scanf("%d%d",&s,&t),s!=-1&&t!=-1)
{
int sf=b[s],st=b[t];
b[s]=0;
b[t]=0;
init();
dijkstra(s);
printf("From %d to %d :
",s,t);
printf("Path: ");
print(t);
printf("
");
printf("Total cost : %d
",dis[t]);
b[s]=sf;//
b[t]=st;//
}
}
return 0;
}