北京做网络工程公司的网站,网站后台维护费用,建筑有限公司官网,wordpress上传ppt时间限制 : 1 秒
内存限制 : 128 MB
C 城可以视为由 n个结点与 m条边组成的无向图。这些结点依次以1,2,....n标号#xff0c;边依次以 1,2...m标号。第i条边#xff08;1im #xff09;连接编号为ui 与vi的结点#xff0c;长度为li米。 小 A 的学校坐落在 C 城中…时间限制 : 1 秒
内存限制 : 128 MB
C 城可以视为由 n个结点与 m条边组成的无向图。这些结点依次以1,2,....n标号边依次以 1,2...m标号。第i条边1im 连接编号为ui 与vi的结点长度为li米。 小 A 的学校坐落在 C 城中编号为 s的结点。小 A 的同学们共有 q位他们想在保证不迟到的前提下每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校于是找到了聪明的小 A。第 i位同学1iq 告诉小 A他的 家位于编号为hi 的结点并且他每秒能行走 1 米。请你帮小 A 计算每位同学从家出发需要多少秒才能到达学校呢
输入
第一行四个正整数n,m,s,q 分别表示 C 城的结点数与边数学校所在的结点编号以及小 A 同学们的数量。 接下来m行每行三个正整数ui,vi,li 表示 C 城中的一条无向边。 接下来q行每行一个正整数hi表示一位同学的情况
输出
共q行对于每位同学输出一个整数表示从家出发到学校的最短时间。
样例
输入 5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4 输出 4
3
1 提示
数据范围
对于 20% 的测试点保证q1 。对于另外20 % 的测试点保证1n500 1m500 。
对于所有测试点保证1n2 * 10^5 1m2 * 10^5 1q2 * 10^51ui,vi,s,hin 1li10^6 。保证给定的图联通。
———————————————————————————————————————————思路
以学校为原始的点Dijkstra算法求学校到每一个点的时间。
代码
#includebits/stdc.h
using namespace std;
const int N200002;
int n,m,s,t,dis[N];
bool v[N];
struct node
{int v,e;
};
vectornode q[N];
priority_queuepairint,intQ;
int main()
{scanf(%d%d%d%d,n,m,s,t);for(int i1;im;i){int a,b,c;scanf(%d%d%d,a,b,c);q[a].push_back(node{c,b});q[b].push_back(node{c,a});}for(int i1;in;i){dis[i]INT_MAX;}dis[s]0;memset(v,0,sizeof(v));while(!Q.empty()) Q.pop();Q.push(make_pair(0,s));while(!Q.empty()){int wzQ.top().second;Q.pop();v[wz]1;for(int i0;iq[wz].size();i){if(dis[q[wz][i].e]dis[wz]q[wz][i].v){dis[q[wz][i].e]dis[wz]q[wz][i].v;if(!v[q[wz][i].e]){Q.push(make_pair(-dis[q[wz][i].e],q[wz][i].e));}}}}for(int i1;it;i){int d;scanf(%d,d);printf(%d\n,dis[d]);}return 0;
}
