牛客プログラミングサミットS 1第6戦-黄金&ダイヤモンド&王者C.dijkstra
16279 ワード
リンク:https://ac.nowcoder.com/acm/contest/6629/C出典:牛客網
タイトルは牛と牛妹が星のシミュレーションゲームをしていることを説明し、ゲームのルールは以下の通りです.
ゲームマップにはn個の星があり、m個のトンネルが接続されている.どのトンネルも双方向で、2つの星の間にトンネルが1つしかないとは限らない.現在、牛はこのnつの星の中のpつの星を占領し、牛妹はこのnつの星の中のqの星を占領している(星ごとに最大1人しか占領できない).今、牛は彼が占領したpつの星の中で任意の星を知りたいと思っています.牛妹が占領したqつの星の中で任意の星まで、この2つの星の最短距離はいくらですか.
例1入力レプリケーション[1],[3,4],[[1,2,7],[2,3,6],[3,4,2],[1,3,11],[2,4,3]],4出力レプリケーション10は、最も近い牛星と牛妹星が1と4であり、それらの間の距離が10であることを示す
例2入力レプリケーション[1],[2],[],2出力レプリケーション-1は、すべての牛牛星と牛妹星が接続されていないことを示しているので、出力-1
備考:50%データ:2leq nleq 100,0leq mleq 200,1leq 200,1leq mleq 200,1leq pleq 5,1leqleqleq 5,p+qleqleq n,1leq wi leq 1 e 42≦n≦100,0≦m≦200,1≦p≦5,1≦q≦5,p+q≦n,1≦wi≦1 e 4 100%データ:2leq nleq nleq 1 e 5,0leq mleq 2 e 5,1 0 0leq pleq 5,1 e 5,1 0leqleq 5,1 e 5,1leqleqleqleq 1 e 5,p+qleq n,min(p,q)leq 10,1leq wileq 1 e 42≦n≦1 e 5,0≦m≦2 e 5,1≦p≦1 e 5,1≦q≦1 e 5,p+q≦n,min(p,q)≦10,1≦wi≦1 e 4関連パラメータは、niuniu牛が占領したp星の番号niumei牛妹が占領したq星の番号path m本のトンネルを意味し、各トンネルにはui,vi,wiの3つの数がある.ui,viはそれぞれトンネルの両側の星の番号で、wiはそれらの間の距離nn int整型星の個数nです
タイトルは牛と牛妹が星のシミュレーションゲームをしていることを説明し、ゲームのルールは以下の通りです.
ゲームマップにはn個の星があり、m個のトンネルが接続されている.どのトンネルも双方向で、2つの星の間にトンネルが1つしかないとは限らない.現在、牛はこのnつの星の中のpつの星を占領し、牛妹はこのnつの星の中のqの星を占領している(星ごとに最大1人しか占領できない).今、牛は彼が占領したpつの星の中で任意の星を知りたいと思っています.牛妹が占領したqつの星の中で任意の星まで、この2つの星の最短距離はいくらですか.
例1入力レプリケーション[1],[3,4],[[1,2,7],[2,3,6],[3,4,2],[1,3,11],[2,4,3]],4出力レプリケーション10は、最も近い牛星と牛妹星が1と4であり、それらの間の距離が10であることを示す
例2入力レプリケーション[1],[2],[],2出力レプリケーション-1は、すべての牛牛星と牛妹星が接続されていないことを示しているので、出力-1
備考:50%データ:2leq nleq 100,0leq mleq 200,1leq 200,1leq mleq 200,1leq pleq 5,1leqleqleq 5,p+qleqleq n,1leq wi leq 1 e 42≦n≦100,0≦m≦200,1≦p≦5,1≦q≦5,p+q≦n,1≦wi≦1 e 4 100%データ:2leq nleq nleq 1 e 5,0leq mleq 2 e 5,1 0 0leq pleq 5,1 e 5,1 0leqleq 5,1 e 5,1leqleqleqleq 1 e 5,p+qleq n,min(p,q)leq 10,1leq wileq 1 e 42≦n≦1 e 5,0≦m≦2 e 5,1≦p≦1 e 5,1≦q≦1 e 5,p+q≦n,min(p,q)≦10,1≦wi≦1 e 4関連パラメータは、niuniu牛が占領したp星の番号niumei牛妹が占領したq星の番号path m本のトンネルを意味し、各トンネルにはui,vi,wiの3つの数がある.ui,viはそれぞれトンネルの両側の星の番号で、wiはそれらの間の距離nn int整型星の個数nです
const int maxn=1e6+5;
int tot,xx,yy;
int vis[maxn],dis[maxn],head[maxn];
class Solution {
public:
/**
*
* @param niuniu int vector p
* @param niumei int vector q
* @param path int vector> m , ui,vi,wi。ui,vi ,wi
* @param nn int n
* @return int
*/
struct node{
int v,w;
bool operator<(const node &a)const{
return w>a.w;
}
};
struct edge{
int to,next,w;
}e[maxn];
void add(int x,int y,int z){
e[++tot].to=y;
e[tot].w=z;
e[tot].next=head[x];
head[x]=tot;
}
void dijkstra(){
priority_queue<node>q;
memset(dis,0x3f,sizeof(dis));
dis[xx]=0;
q.push(node{xx,dis[xx]});
while(!q.empty()){
int v=q.top().v;
q.pop();
if(v==yy)return ;
if(vis[v])continue;
vis[v]=1;
for(int i=head[v];i;i=e[i].next){
int u=e[i].to;
int w=e[i].w;
if(dis[u]>dis[v]+w){
dis[u]=dis[v]+w;
q.push(node{u,dis[u]});
}
}
}
}
int Length(vector<int>& nn, vector<int>& nm, vector<vector<int> >& path, int n) {
for(auto &i:path){
add(i[0],i[1],i[2]);
add(i[1],i[0],i[2]);
}
xx=n+1,yy=n+2;
for(auto &i:nn){
add(xx,i,0);
add(i,xx,0);
}
for(auto &i:nm){
add(i,yy,0);
add(yy,i,0);
}
dijkstra();
if(dis[yy]==0x3f3f3f3f)return -1;
return dis[yy];
}
};