#include<cstdio>
using namespace std;
int dis[25001],u[25001],v[25001],w[25001],inf=99999999;
int main()
{
int i,j,n,m,ans=-1,s,b,o,p,pd;
scanf("%d%d%d",&n,&m,&b);
for(i=1;i<=m;++i)scanf("%d%d%d",&u[i],&v[i],&w[i]);
for(i=1;i<=n;++i)dis[i]=inf;dis[1]=0;
for(j=1;j<n;++j)
for(i=1;i<=m;++i)
{
if(dis[v[i]]>dis[u[i]]+w[i])
{
dis[v[i]]=dis[u[i]]+w[i];
pd=0;
}
if(dis[u[i]]>dis[v[i]]+w[i])
{
dis[u[i]]=dis[v[i]]+w[i];
pd=0;
}
if(pd)break;
}
for(i=1;i<=n;++i)printf("%d ",dis[i]);
for(i=1;i<=b;++i)
{
scanf("%d%d",&o,&p);
printf("%d\n",dis[p]+dis[o]);
}
return 0;
}
by zhangyuxing @ 2018-02-02 19:36:47
样例过
by zhangyuxing @ 2018-02-02 19:38:20
删帖
by zhangyuxing @ 2018-02-02 19:40:23
```
include<cstdio>
using namespace std;
int dis[25001],u[25001],v[25001],w[25001],inf=99999999;
int main()
{
int i,j,n,m,ans=-1,s,b,o,p,pd;
scanf("%d%d%d",&n,&m,&b);
for(i=1;i<=m;++i)scanf("%d%d%d",&u[i],&v[i],&w[i]);
for(i=1;i<=n;++i)dis[i]=inf;dis[1]=0; for(j=1;j<n;++j)
for(i=1;i<=m;++i)
{ if(dis[v[i]]>dis[u[i]]+w[i])
{
dis[v[i]]=dis[u[i]]+w[i];
pd=0;
}
if(dis[u[i]]>dis[v[i]]+w[i])
{
dis[u[i]]=dis[v[i]]+w[i];
pd=0;
}
if(pd)break;
}
for(i=1;i<=n;++i)
printf("%d ",dis[i]);
for(i=1;i<=b;++i)
{
scanf("%d%d",&o,&p);
printf("%d\n",dis[p]+dis[o]);
}
return 0;
}
```
by 稀神探女 @ 2018-02-02 19:41:31
#include<cstdio>
using namespace std;
int dis[90001],u[90001],v[90001],w[90001],inf=99999999;
int main()
{
int i,j,n,m,ans=-1,s,b,o,p,pd;
scanf("%d%d%d",&n,&m,&b);
for(i=1;i<=m;++i)scanf("%d%d%d",&u[i],&v[i],&w[i]);
for(i=1;i<=n;++i)dis[i]=inf;dis[1]=0;
for(j=1;j<n;++j)
for(i=1;i<=m;++i)
{
if(dis[v[i]]>dis[u[i]]+w[i])
{
dis[v[i]]=dis[u[i]]+w[i];
pd=0;
}
if(dis[u[i]]>dis[v[i]]+w[i])
{
dis[u[i]]=dis[v[i]]+w[i];
pd=0;
}
if(pd)break;
}
for(i=1;i<=b;++i)
{
scanf("%d%d",&o,&p);
printf("%d\n",dis[p]+dis[o]);
}
return 0;
}
by zhangyuxing @ 2018-02-02 19:49:27
不删了
by zhangyuxing @ 2018-02-02 19:49:58
希望更丰富的展现?使用[Markdown](https://www.luogu.org/wiki/show?name=帮助:markdown)
by MicroMaker @ 2019-03-19 19:54:31