中国建筑总公司网站,如今做那个网站能致富,wordpress调用网站最新文章,asp网站下载香甜的黄油 Sweet Butter 黄油真的是这么做的吗#xff1f;#xff01;#xff01;#xff01;[惶恐] 这道题是Dijkstra算法的简单变形 通过题意我们要找到一个点使奶牛所在点的路程和最短。通过Dijkstra的模板我们可以求的一点到其他任一点的最短路径#xff0c;那么我们…香甜的黄油 Sweet Butter 黄油真的是这么做的吗[惶恐] 这道题是Dijkstra算法的简单变形 通过题意我们要找到一个点使奶牛所在点的路程和最短。通过Dijkstra的模板我们可以求的一点到其他任一点的最短路径那么我们可以遍历所有点跑一边Dijkstra每个点的最后把奶牛所在点的dis相加最后将每个点的路程和进行比较输出最短。 AC代码如下 #includeiostream
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includequeue
#includevector
#define INF 0x3f3f3f3f
#define MAXN 1000
using namespace std;vectorint G[MAXN];
vectorint M[MAXN];int cow[MAXN];
int dis[MAXN];
int done[MAXN];struct item
{int u;int dis;friend bool operator (struct item x,struct item y){return x.disy.dis;}
};priority_queueitem q;
int mnINF;
int main()
{int n,p,c;scanf(%d%d%d,n,p,c);for(int i1;in;i){scanf(%d,cow[i]);}for(int i1;ic;i){int x,y,z;scanf(%d%d%d,x,y,z);G[x].push_back(y);M[x].push_back(z);G[y].push_back(x);M[y].push_back(z);}for(int i1;ip;i){memset(dis,0x3f,sizeof(dis));memset(done,0,sizeof(done));q.push((item){i,0});dis[i]0;while(!q.empty()){item r;rq.top();q.pop();int aur.u;if(done[au]) continue;done[au]1;for(int j0;jG[au].size();j){int pG[au][j];int cdis[au]M[au][j];if(dis[p]c){dis[p]c;q.push((item){p,c});}}}int total0;for(int j1;jn;j){if(cow[j]INF) continue;totaltotaldis[cow[j]];}mnmin(mn,total);}printf(%d,mn);return 0;
} 转载于:https://www.cnblogs.com/LITTLESUNwl/p/10757313.html
