建站推荐,深圳网络优化公司,网站开发网页加载很慢怎么办,北京广告公司工资有一个邮递员要送东西#xff0c;邮局在节点 1 1 1。他总共要送 n − 1 n−1 n−1样东西#xff0c;其目的地分别是节点 2 2 2到节点 n n n。所有的道路都是单行的#xff0c;共有 m m m条道路。邮递员每次只能带一样东西#xff0c;运送每件物品过后必须返回邮局。求送完东…有一个邮递员要送东西邮局在节点 1 1 1。他总共要送 n − 1 n−1 n−1样东西其目的地分别是节点 2 2 2到节点 n n n。所有的道路都是单行的共有 m m m条道路。邮递员每次只能带一样东西运送每件物品过后必须返回邮局。求送完东西后回到邮局最少需要的时间。 首先送信时从 1 1 1到 2 − n 2-n 2−n就是标准的单源最短路而返回的时候就是多到一多源最短路比较麻烦。这时候我们邻接矩阵倒过来从多到一的最短路变式的路径“反向建边”就变成一到多的单源最短路。
#includebits/stdc.h
using namespace std;
struct node
{int u,v,w,next;
}a[100010],b[100010];
struct New
{int w,now;bool operator (const New x)const{return wx.w;}
};
priority_queue New q;
int head[10010],bhead[10010],dis[10010],flag[10010];
int n,m,s,num1,num2,ans0,x,y;
void add(int u,int v,int w)
{a[num1].vv;a[num1].ww;a[num1].nexthead[u];head[u]num1;b[num2].vu;b[num2].ww;b[num2].nextbhead[v];bhead[v]num2;
}
void Dij()
{for(int i1;in;i)dis[i]9999999;dis[1]0;memset(flag,0,sizeof(flag));q.push((New){0,1});while(!q.empty()){New Xq.top();q.pop();int UX.now;if(flag[U]1)continue;flag[U]1;for(int ihead[U];i;ia[i].next){int Va[i].v;if(dis[V]dis[U]a[i].w){dis[V]dis[U]a[i].w;q.push((New){dis[V],V});}}}
}
void Dij2()
{for(int i1;in;i)dis[i]9999999;memset(flag,0,sizeof(flag));dis[1]0;q.push((New){0,1});while(!q.empty()){New Xq.top();q.pop();int UX.now;if(flag[U]1)continue;flag[U]1;for(int ibhead[U];i;ib[i].next){int Vb[i].v;if(dis[V]dis[U]b[i].w){dis[V]dis[U]b[i].w;q.push((New){dis[V],V});}}}
}
int main()
{cinnm;for(int i1;im;i){cinxys;add(x,y,s);}Dij();for(int i2;in;i)ansdis[i];Dij2();for(int i2;in;i)ansdis[i];coutansendl;return 0;
}
