PIPI OJ 1286: PIPI运货(单源最短路径+边有权值+顶点也有权值)

本文主要是介绍PIPI OJ 1286: PIPI运货(单源最短路径+边有权值+顶点也有权值)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1286: PIPI运货

菜鸟生成记(16)

这又是一个单源最短路径的模板题,有一点点加强,顶点加权;

不过把模板稍改一下就可以了;

水题真的很上头,一写就停不下来;

#include<bits/stdc++.h>
using namespace std;
const int N=1e+3+10,inf=1e+8+10;
int cost[N];
int Map[N][N];
int dis[N];
int book[N];
int n;
int find()//
{int min1=inf,t=-1;for(int i=1;i<=n;i++){if(book[i]==0&&dis[i]<min1){min1=dis[i];t=i;}}return t;
}
void djk(int x,int y)
{for(int i=1;i<=n;i++)dis[i]=Map[x][i];int u=x;book[u]=1;for(int i=1;i<n;i++){u=find();book[u]=1;for(int j=1;j<=n;j++){if(book[j]==0&&dis[j]>dis[u]+Map[u][j]+cost[u])dis[j]=dis[u]+Map[u][j]+cost[u];//这里加个顶点的权值}if(u==y)//终点判断(没有这个判断会超时25%)break;//到终点直接结束}
}
int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>Map[i][j];if(Map[i][j]==-1)Map[i][j]=inf;}}int x,y,d;for(int i=1;i<=n;i++)cin>>cost[i];cin>>d;while(d--){cin>>x>>y;djk(x,y);cout<<dis[y]<<endl;memset(dis,0,sizeof(dis));memset(book,0,sizeof(book));}return 0;
}

这篇关于PIPI OJ 1286: PIPI运货(单源最短路径+边有权值+顶点也有权值)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---