H.武
链接：
这个题写的有点想发脾气，自己的板子垃圾了，这个题要用优先队列优化版的迪杰斯特拉的板子才可以过，但是自己太智障了，段错误，编译错误，段错误，内存超限，运行超时，段错误，a了。
不想说什么了，简直蠢到家了。
代码(学长的板子就是好):
1 //H-学长的模板 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std;12 typedef long long ll;13 const int maxn=1e5+10;14 const double eps=1e-7;15 const int N=1e5+10;16 const int INF=0x3f3f3f3f; 17 18 19 int head[N*2], nex[N*2], to[N*2], val[N*2], dis[N], vis[N], tot; 20 21 struct cmp{ 22 bool operator()(int a,int b) { 23 return dis[a]>dis[b]; 24 } 25 }; 26 27 priority_queue
, cmp > Q; 28 29 void init() { 30 tot = 0; 31 while(!Q.empty()) Q.pop(); 32 memset(head, -1, sizeof(head)); 33 memset(dis, 127, sizeof(dis)); 34 memset(vis, 0, sizeof(vis)); 35 } 36 37 void addedge(int u, int v, int w) { 38 to[tot] = v; 39 nex[tot] = head[u]; 40 val[tot] = w; 41 head[u] = tot++; 42 } 43 44 void Dijkstra(int S) { 45 Q.push(S); 46 dis[S] = 0, vis[S] = 1; 47 while(!Q.empty()) { 48 int u = Q.top(); 49 Q.pop(); 50 for(int i=head[u]; i!=-1; i=nex[i]) { 51 int v = to[i]; 52 if(!vis[v] && dis[u]+val[i] < dis[v]) { 53 dis[v] = dis[u]+val[i]; 54 Q.push(v), vis[v] = 1; 55 } 56 } 57 } 58 } 59 60 int main(){ 61 int n,p,k; 62 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 63 init(); 64 cin>>n>>p>>k; 65 for(int i=0;i
>u>>v>>w; 68 addedge(u,v,w); 69 addedge(v,u,w); 70 } 71 Dijkstra(p); 72 sort(dis+1,dis+1+n); 73 cout< <