1 var
 2     n,m,i,x,tot,j                                 :longint;
 3     prime                                         :array[0..10000050] of boolean;
 4     p                                             :array[0..10000050] of longint;
 5 begin
 6     read(n,m);
 7     for i:=2 to n do
 8     begin
 9         if not prime[i] then
10         begin
11             inc(tot);
12             p[tot]:=i;
13         end;
14         for j:=1 to tot do
15         begin
16             if (i*p[j]>n) then break;
17             prime[i*p[j]]:=true;
18             if i mod p[j]=0 then break;
19         end;
20     end;
21     //for i:=1 to tot do prime[p[i]]:=true;
22     for i:=1 to m do
23     begin
24         read(x);
25         if x=1 then writeln(‘No‘) else 
26         if (prime[x]) then writeln(‘No‘) else writeln(‘Yes‘);
27     end;
28 end.

 1 var
 2     n,i,j,tot                                   :longint;
 3     nprime                                     :array[0..10000050] of boolean;
 4     p,phi                                    :array[0..10000050] of int64;
 5 begin
 6     read(n);
 7     phi[1]:=1;
 8     for i:=2 to n do
 9     begin
10         if not nprime[i] then
11         begin
12             phi[i]:=i-1;
13             inc(tot);
14             p[tot]:=i;
15         end;
16         for j:=1 to tot do
17         begin
18             if (i*p[j]>n) then break;
19             nprime[i*p[j]]:=true;
20             if (i mod p[j]=0) then
21             begin
22                 phi[i*p[j]]:=phi[i]*p[j];
23                 break;
24             end else phi[i*p[j]]:=phi[i]*(p[j]-1);
25         end;
26     end;
27     for i:=n to n do write(phi[i],‘ ‘);
28 end.

 1 var
 2     n,i,j,tot                                 :longint;
 3     nprime                                     :array[0..1000050] of boolean;
 4     p,miu                                     :array[0..1000050] of longint;
 5 begin
 6     read(n);
 7     miu[1]:=1;
 8     for i:=2 to n do
 9     begin
10         if not nprime[i] then
11         begin
12             miu[i]:=-1;
13             inc(tot);
14             p[tot]:=i;
15         end;
16         for j:=1 to tot do
17         begin
18             if i*p[j]>n then break;
19             nprime[i*p[j]]:=true;
20             if (i mod p[j]=0) then
21             begin
22                 miu[i*p[j]]:=0;
23                 break;
24             end else miu[i*p[j]]:=-miu[i];
25         end;
26     end;
27     for i:=1 to n do write(miu[i],‘ ‘);
28 end.

  1 const maxn=2000000;
  2 var
  3     N,L,T,LL                                    :int64;
  4     nprime                                         :Array[0..2000050] of boolean;
  5     p                                             :array[0..200050] of longint;
  6     pre                                         :array[0..2000050] of longint;
  7     pr                                             :array[0..2000050] of longint;
  8     las,other,len                                 :array[0..2000050] of int64;
  9     la,oth,le                                     :array[0..2000050] of longint;
 10     miu                                         :array[0..2000050] of longint;
 11     phi                                            :array[0..2000050] of int64;
 12     tot,i                                         :longint;
 13     a,b                                         :double;
 14 
 15 procedure pred();
 16 var
 17     i,j                                     :longint;
 18 begin
 19     miu[1]:=1;
 20     phi[1]:=1;
 21     for i:=2 to maxn do
 22     begin
 23         if not nprime[i] then 
 24         begin
 25             miu[i]:=-1;
 26             phi[i]:=i-1;
 27             inc(tot);
 28             p[tot]:=i;
 29         end;
 30         for j:=1 to tot do
 31         begin
 32             if i*p[j]>maxn then break;
 33             nprime[i*p[j]]:=true;
 34             if i mod p[j]=0 then
 35             begin
 36                 miu[i*p[j]]:=0;
 37                 phi[i*p[j]]:=int64(phi[i]*p[j]);
 38                 break;
 39             end else 
 40             begin
 41                 miu[i*p[j]]:=-miu[i];
 42                 phi[i*p[j]]:=phi[i]*(p[j]-1);
 43             end;
 44         end;
 45     end;
 46     for i:=1 to maxn do miu[i]:=miu[i-1]+miu[i];
 47     for i:=1 to maxn do phi[i]:=phi[i-1]+phi[i];
 48 end;
 49 
 50 procedure add(u,v,r:int64);
 51 begin
 52     inc(L);
 53     pre[L]:=las[u];
 54     las[u]:=L;
 55     other[L]:=v;
 56     len[L]:=r;
 57 end;
 58 
 59 function cal1(x:int64):int64;
 60 var
 61     ans,z,i,j,last                                :int64;
 62     pp,q,k,di                                    :int64;
 63 begin
 64     if x<=maxn then exit(phi[x]);
 65     k:=x mod maxn;
 66     ans:=0;
 67     pp:=las[k];
 68     while pp<>0 do
 69     begin
 70         q:=other[pp];
 71         if q=x then exit(len[pp]);
 72         pp:=pre[pp];
 73     end;
 74     i:=2;
 75     while i<=x do
 76     begin
 77         di:=x div i;
 78         last:=x div di;
 79         ans:=ans+(last-i+1)*cal1(di);
 80         i:=last+1;
 81     end;
 82     ans:=int64(x*(x+1) div 2-ans);
 83     add(k,x,ans);
 84     exit(ans);
 85 end;
 86 
 87 procedure ad(u,v,r:longint);
 88 begin
 89     inc(LL);
 90     pr[LL]:=la[u];
 91     la[u]:=LL;
 92     oth[LL]:=v;
 93     le[LL]:=r;
 94 end;
 95 
 96 function cal2(x:longint):longint;
 97 var
 98     last,i,di                                 :int64;
 99     ans                                     :longint;
100     pp,q,k                                     :longint;
101 begin
102     if x<=maxn then exit(miu[x]);
103     k:=x mod maxn;
104     ans:=0;
105     pp:=la[k];
106     while pp<>0 do
107     begin
108         q:=oth[pp];
109         if q=x then exit(le[pp]);
110         pp:=pr[pp];
111     end;
112     i:=2;
113     while i<=x do
114     begin
115         di:=x div i;
116         last:=x div di;
117         ans:=ans+(last-i+1)*cal2(di);
118         i:=last+1;
119     end;
120     ans:=1-ans;
121     ad(k,x,ans);
122     exit(ans);
123 end;
124 
125 begin
126     read(T);
127     pred;
128     for i:=1 to T do
129     begin
130         read(N);
131         writeln(cal1(N),‘ ‘,cal2(N));
132     end;
133     //writeln(a);
134 end.

 1 var
 2     N,i,j,tot,w                                :longint;
 3     nprime                                     :array[0..1000050] of boolean;
 4     p                                         :array[0..1000050] of longint;
 5     f,t                                     :array[0..1000050] of int64;
 6 begin
 7     read(N);
 8     f[1]:=1;
 9     for i:=2 to N do
10     begin
11         if not nprime[i] then
12         begin
13             inc(tot);
14             p[tot]:=i;
15             f[i]:=i+1;
16             t[i]:=i;
17         end;
18         for j:=1 to tot do
19         begin
20             if i*p[j]>N then break;
21             nprime[i*p[j]]:=true;
22             if (i mod p[j]=0) then
23             begin
24                 t[i*p[j]]:=t[i]*p[j];
25                 if i*p[j]=t[i*p[j]] then
26                 begin
27                     w:=1;
28                     while w<=i*p[j] do
29                     begin
30                         f[i*p[j]]:=f[i*p[j]]+w;
31                         w:=w*p[j];
32                     end;
33                 end else f[i*p[j]]:=f[i*p[j] div t[i*p[j]]]*f[t[i*p[j]]];
34                 break;
35             end;
36             t[i*p[j]]:=p[j];
37             f[i*p[j]]:=f[i]*f[p[j]];
38         end;
39     end;
40     for i:=1 to N do write(f[i],‘ ‘);
41 end.

  1 var
  2     N,i,opt,x,t,tot                                 :longint;
  3     left,right,size,key                             :Array[0..100050] of longint;
  4 
  5 procedure lrot(var t:longint);
  6 var
  7     k                                                 :longint;
  8 begin
  9     k:=right[t];
 10     right[t]:=left[k];
 11     left[k]:=t;
 12     size[k]:=size[t];
 13     size[t]:=size[left[t]]+size[right[t]]+1;
 14     t:=k;
 15 end;
 16 
 17 procedure rrot(var t:longint);
 18 var
 19     k                                                 :longint;
 20 begin
 21     k:=left[t];
 22     left[t]:=right[k];
 23     right[k]:=t;
 24     size[k]:=size[t];
 25     size[t]:=size[left[t]]+size[right[t]]+1;
 26     t:=k;
 27 end;
 28 
 29 procedure maintain(var t:longint; flag:boolean);
 30 begin
 31     if not flag then
 32     begin
 33         if size[left[left[t]]]>size[right[t]] then rrot(t) else
 34         if size[right[left[t]]]>size[right[t]] then
 35         begin
 36             lrot(left[t]);
 37             rrot(t);
 38         end else exit;
 39     end else
 40     begin
 41         if size[right[right[t]]]>size[left[t]] then lrot(t) else
 42         if size[left[right[t]]]>size[left[t]] then
 43         begin
 44             rrot(right[t]);
 45             lrot(t);
 46         end else exit;
 47     end;
 48     maintain(left[t],false);
 49     maintain(right[t],true);
 50     maintain(t,false);
 51     maintain(t,true);
 52 end;
 53 
 54 procedure insert(var t:longint; v:longint);
 55 begin
 56     if t=0 then
 57     begin
 58         inc(tot);
 59         t:=tot;
 60         left[t]:=0;
 61         right[t]:=0;
 62         size[t]:=1;
 63         key[t]:=v;
 64         exit;
 65     end;
 66     inc(size[t]);
 67     if v<key[t] then insert(left[t],v) else insert(right[t],v);
 68     maintain(t,v>=key[t]);
 69 end;
 70 
 71 function delete(var t:longint; v:longint):longint;
 72 begin
 73     dec(size[t]);
 74     if (v=key[t]) or ((v<key[t]) and (left[t]=0)) or ((v>key[t]) and (right[t]=0)) then
 75     begin
 76         delete:=key[t];
 77         if (left[t]=0) or (right[t]=0) then t:=left[t]+right[t] else key[t]:=delete(left[t],v+1);
 78     end else
 79     if v<key[t] then exit(delete(left[t],v)) else exit(delete(right[t],v));
 80 end;
 81 
 82 function rank(var t:longint; v:longint):longint;
 83 begin
 84     if t=0 then exit(1);
 85     if v<=key[t] then exit(rank(left[t],v));
 86     exit(rank(right[t],v)+size[left[t]]+1);
 87 end;
 88 
 89 function select(var t:longint; v:longint):longint;
 90 begin
 91     if v=size[left[t]]+1 then exit(key[t]);
 92     if v<size[left[t]]+1 then exit(select(left[t],v));
 93     exit(select(right[t],v-size[left[t]]-1));
 94 end;
 95 
 96 function pred(var t:longint; v:longint):longint;
 97 begin
 98     if t=0 then exit(-1);
 99     if v<=key[t] then exit(pred(left[t],v));
100     pred:=pred(right[t],v);
101     if pred=-1 then exit(key[t]);
102 end;
103 
104 function succ(var t:longint; v:longint):longint;
105 begin
106     if t=0 then exit(-1);
107     if v>=key[t] then exit(succ(right[t],v));
108     succ:=succ(left[t],v);
109     if succ=-1 then exit(key[t]);
110 end;
111 
112 begin
113     read(N);
114     for i:=1 to N do
115     begin
116         read(opt,x);
117         if (opt=1) then insert(t,x) else 
118         if (opt=2) then x:=delete(t,x) else
119         if (opt=3) then writeln(rank(t,x)) else
120         if (opt=4) then writeln(select(t,x)) else
121         if (opt=5) then writeln(pred(t,x)) else
122         if (opt=6) then writeln(succ(t,x));
123     end;
124 end.

  1 type
  2     rec                                         =record
  3         l,r                                     :longint;
  4         sum,lz,tg                                 :int64;
  5     end;
  6 
  7 var
  8     t                                             :array[0..300050] of rec;
  9     a                                             :array[0..100050] of int64;
 10     N,M,mo,i,opt,x,y                             :longint;
 11     z                                             :int64;
 12 
 13 procedure build(x,l,r:longint);
 14 var
 15     mid                                         :longint;
 16 begin
 17     t[x].l:=l; t[x].r:=r; t[x].tg:=1;
 18     if (t[x].l=t[x].r) then
 19     begin
 20         t[x].sum:=a[l] mod mo;
 21         exit;
 22     end;
 23     mid:=(t[x].l+t[x].r)>>1;
 24     build(x*2,l,mid);
 25     build(x*2+1,mid+1,r);
 26     t[x].sum:=(t[x*2].sum+t[x*2+1].sum) mod mo;
 27 end;
 28 
 29 procedure update(x:longint);
 30 begin
 31     t[x].sum:=(t[x].sum*t[x].tg+t[x].lz*(t[x].r-t[x].l+1)) mod mo;
 32     if (t[x].l=t[x].r) then
 33     begin
 34         t[x].tg:=1;
 35         t[x].lz:=0;
 36         exit;
 37     end;
 38     t[x*2].tg:=(t[x*2].tg*t[x].tg) mod mo;
 39     t[x*2+1].tg:=(t[x*2+1].tg*t[x].tg) mod mo;
 40     t[x*2].lz:=(t[x*2].lz*t[x].tg+t[x].lz) mod mo;
 41     t[x*2+1].lz:=(t[x*2+1].lz*t[x].tg+t[x].lz) mod mo;
 42     t[x].tg:=1;
 43     t[x].lz:=0;
 44 end;
 45 
 46 procedure c_tg(x,l,r:longint; y:int64);
 47 var
 48     mid                                         :longint;
 49 begin
 50     if (t[x].lz<>0) or (t[x].tg<>1) then update(x);
 51     if (t[x].l=l) and (t[x].r=r) then
 52     begin
 53         t[x].tg:=(t[x].tg*y) mod mo;
 54         exit;
 55     end;
 56     mid:=(t[x].l+t[x].r)>>1;
 57     if l>mid then c_tg(x*2+1,l,r,y) else
 58     if r<=mid then c_tg(x*2,l,r,y) else
 59     begin
 60         c_tg(x*2,l,mid,y);
 61         c_tg(x*2+1,mid+1,r,y);
 62     end;
 63     t[x].sum:=(t[x*2].sum*t[x*2].tg+t[x*2].lz*(t[x*2].r-t[x*2].l+1)+
 64         t[x*2+1].sum*t[x*2+1].tg+t[x*2+1].lz*(t[x*2+1].r-t[x*2+1].l+1)) mod mo;
 65 end;
 66 
 67 procedure c_lz(x,l,r:longint; y:int64);
 68 var
 69     mid                                         :longint;
 70 begin
 71     if (t[x].lz<>0) or (t[x].tg<>1) then update(x);
 72     if (t[x].l=l) and (t[x].r=r) then
 73     begin
 74         t[x].lz:=(t[x].lz+y) mod mo;
 75         exit;
 76     end;
 77     mid:=(t[x].l+t[x].r)>>1;
 78     if l>mid then c_lz(x*2+1,l,r,y) else
 79     if r<=mid then c_lz(x*2,l,r,y) else
 80     begin
 81         c_lz(x*2,l,mid,y);
 82         c_lz(x*2+1,mid+1,r,y);
 83     end;
 84     t[x].sum:=(t[x*2].sum*t[x*2].tg+t[x*2].lz*(t[x*2].r-t[x*2].l+1)+
 85         t[x*2+1].sum*t[x*2+1].tg+t[x*2+1].lz*(t[x*2+1].r-t[x*2+1].l+1)) mod mo;
 86 end;
 87 
 88 function find(x,l,r:longint):int64;
 89 var
 90     mid                                         :longint;
 91 begin
 92     if (t[x].lz<>0) or (t[x].tg<>1) then update(x);
 93     if (t[x].l=l) and (t[x].r=r) then exit(t[x].sum mod mo);
 94     mid:=(t[x].l+t[x].r)>>1;
 95     if l>mid then exit(find(x*2+1,l,r)) else
 96     if r<=mid then exit(find(x*2,l,r)) else
 97         exit((find(x*2,l,mid)+find(x*2+1,mid+1,r)) mod mo);
 98 end;
 99 
100 begin
101     read(N,M,mo);
102     for i:=1 to N do read(a[i]);
103     build(1,1,N);
104     for i:=1 to M do
105     begin
106         read(opt);
107         if opt=1 then
108         begin
109             read(x,y,z);
110             c_tg(1,x,y,z);
111         end else
112         if opt=2 then
113         begin
114             read(x,y,z);
115             c_lz(1,x,y,z);
116         end else
117         begin
118             read(x,y);
119             writeln(find(1,x,y));
120         end;
121     end;
122 end.

  1 type
  2     rec                             =record
  3         l,r                         :longint;
  4         sum,lazy                     :int64;
  5     end;
  6 
  7 var
  8     N,M,R,mo,i,x,y,opt,L,tot        :longint;
  9     z                                 :int64;
 10     t                                 :array[0..300050] of rec;
 11     a,key                            :array[0..100050] of int64;
 12     size,num,dep,mson,top,father    :array[0..100050] of longint;
 13     vis                             :array[0..100050] of boolean;
 14     pre,last,other                     :array[0..200050] of longint;
 15 
 16 procedure swap(var x,y:longint);
 17 var
 18     z                                 :longint;
 19 begin
 20     z:=x;
 21     x:=y;
 22     y:=z;
 23 end;
 24 
 25 procedure add(u,v:longint);
 26 begin
 27     inc(L);
 28     pre[L]:=last[u];
 29     last[u]:=L;
 30     other[L]:=v;
 31 end;
 32 
 33 procedure dfs(x,fa:longint);
 34 var
 35     p,q                             :longint;
 36 begin
 37     size[x]:=1;
 38     p:=last[x];
 39     while p<>0 do
 40     begin
 41         q:=other[p];
 42         if q<>fa then
 43         begin
 44             father[q]:=x;
 45             dfs(q,x);
 46             size[x]:=size[x]+size[q];
 47             if size[q]>size[mson[x]] then mson[x]:=q;
 48         end;
 49         p:=pre[p];
 50     end;
 51 end;
 52 
 53 procedure make(x,depp,topp:longint);
 54 var
 55     p,q                             :longint;
 56 begin
 57     inc(tot);
 58     num[x]:=tot;
 59     a[tot]:=key[x];
 60     dep[x]:=depp;
 61     top[x]:=topp;
 62     if mson[x]<>0 then
 63     begin
 64         vis[mson[x]]:=true;
 65         make(mson[x],depp,topp);
 66     end;
 67     p:=last[x];
 68     while p<>0 do
 69     begin
 70         q:=other[p];
 71         if (vis[q]) or (q=mson[x]) then
 72         begin
 73             p:=pre[p];
 74             continue;
 75         end;
 76         vis[q]:=true;
 77         make(q,depp+1,q);
 78         p:=pre[p];
 79     end;
 80 end;
 81 
 82 procedure build(x,l,r:longint);
 83 var
 84     mid                             :longint;
 85 begin
 86     t[x].l:=l; t[x].r:=r;
 87     if (t[x].l=t[x].r) then
 88     begin
 89         t[x].sum:=a[l] mod mo;
 90         exit;
 91     end;
 92     mid:=(t[x].l+t[x].r)>>1;
 93     build(x*2,l,mid);
 94     build(x*2+1,mid+1,r);
 95     t[x].sum:=(t[x*2].sum+t[x*2+1].sum) mod mo;
 96 end;
 97 
 98 procedure update(x:longint);
 99 begin
100     t[x].sum:=(t[x].sum+t[x].lazy*(t[x].r-t[x].l+1)) mod mo;
101     if (t[x].l=t[x].r) then
102     begin
103         t[x].lazy:=0;
104         exit;
105     end;
106     t[x*2].lazy:=(t[x*2].lazy+t[x].lazy) mod mo;
107     t[x*2+1].lazy:=(t[x*2+1].lazy+t[x].lazy) mod mo;
108     t[x].lazy:=0;
109 end;
110 
111 procedure change(x,l,r:longint;y:int64);
112 var
113     mid                             :longint;
114 begin
115     if (t[x].l=l) and (t[x].r=r) then
116     begin
117         t[x].lazy:=(t[x].lazy+y) mod mo;
118         exit;
119     end;
120     if (t[x].lazy<>0) then update(x);
121     mid:=(t[x].l+t[x].r)>>1;
122     if l>mid then change(x*2+1,l,r,y) else
123     if r<=mid then change(x*2,l,r,y) else
124     begin
125         change(x*2,l,mid,y);
126         change(x*2+1,mid+1,r,y);
127     end;
128     t[x].sum:=(t[x*2].sum+t[x*2].lazy*(t[x*2].r-t[x*2].l+1)+t[x*2+1].sum+t[x*2+1].lazy*(t[x*2+1].r-t[x*2+1].l+1)) mod mo;
129 end;
130 
131 function find(x,l,r:longint):int64;
132 var
133     mid                             :longint;
134 begin
135     if (t[x].lazy<>0) then update(x);
136     if (t[x].l=l) and (t[x].r=r) then exit(t[x].sum);
137     mid:=(t[x].l+t[x].r)>>1;
138     if l>mid then exit(find(x*2+1,l,r)) else
139     if r<=mid then exit(find(x*2,l,r)) else
140         exit((find(x*2,l,mid)+find(x*2+1,mid+1,r)) mod mo);
141 end;
142 
143 procedure qchange(x,y:longint; z:int64);
144 begin
145     if dep[x]>dep[y] then swap(x,y);
146     while dep[y]>dep[x] do
147     begin
148         change(1,num[top[y]],num[y],z);
149         y:=father[top[y]];
150     end;
151     while top[x]<>top[y] do
152     begin
153         change(1,num[top[x]],num[x],z);
154         change(1,num[top[y]],num[y],z);
155         x:=father[top[x]];
156         y:=father[top[y]];
157     end;
158     x:=num[x];
159     y:=num[y];
160     if x>y then swap(x,y);
161     change(1,x,y,z);
162 end;
163 
164 function qfind(x,y:longint):int64;
165 var
166     sum                             :int64;
167 begin
168     sum:=0;
169     if dep[x]>dep[y] then swap(x,y);
170     while dep[y]>dep[x] do
171     begin
172         sum:=(sum+find(1,num[top[y]],num[y])) mod mo;
173         y:=father[top[y]];
174     end;
175     while top[x]<>top[y] do
176     begin
177         sum:=(sum+find(1,num[top[y]],num[y])) mod mo; 
178         sum:=(sum+find(1,num[top[x]],num[x])) mod mo;
179         y:=father[top[y]];        
180         x:=father[top[x]];
181     end;
182     x:=num[x];
183     y:=num[y];
184     if x>y then swap(x,y);
185     exit((sum+find(1,x,y)) mod mo);
186 end;
187 
188 
189 begin
190     read(N,M,R,mo);
191     for i:=1 to N do read(key[i]);
192     for i:=1 to N-1 do
193     begin
194         read(x,y);
195         add(x,y);
196         add(y,x);
197     end;
198     dfs(R,0);
199     //for i:=1 to n do writeln(size[i]);
200     vis[R]:=true;
201     make(R,1,R);
202     build(1,1,N);
203     for i:=1 to M do
204     begin
205         read(opt);
206         if (opt=1) then
207         begin
208             read(x,y,z);
209             qchange(x,y,z);
210         end else
211         if (opt=2) then
212         begin
213             read(x,y);
214             writeln(qfind(x,y));
215         end else
216         if (opt=3) then
217         begin
218             read(x,z);
219             change(1,num[x],num[x]+size[x]-1,z);
220         end else
221         begin
222             read(x);
223             writeln(find(1,num[x],num[x]+size[x]-1));
224         end;
225     end;
226 end.

  1 var
  2     N,M,S,L,i,x,y,z,tot                            :longint;
  3     d,heap,pl                                    :array[0..10005] of longint;
  4     pre,last,other,len                             :array[0..500050] of longint;
  5 
  6 procedure swap(var x,y:longint);
  7 var
  8     z                                             :longint;
  9 begin
 10     z:=x;
 11     x:=y;
 12     y:=z;
 13 end;
 14 
 15 procedure add(u,v,r:longint);
 16 begin
 17     inc(L);
 18     pre[L]:=last[u];
 19     last[u]:=L;
 20     other[L]:=v;
 21     len[L]:=r;
 22 end;
 23 
 24 procedure up(x:longint);
 25 var
 26     i,j                                         :longint;
 27 begin
 28     i:=x;
 29     while i>>1>0 do
 30     begin
 31         j:=i>>1;
 32         if d[heap[j]]<=d[heap[i]] then break;
 33         swap(heap[i],heap[j]);
 34         pl[heap[i]]:=i;
 35         pl[heap[j]]:=j;
 36         i:=j;
 37     end;
 38 end;
 39 
 40 procedure down(x:longint);
 41 var
 42     i,j                                         :longint;
 43 begin
 44     i:=x;
 45     while i<<1<=tot do
 46     begin
 47         j:=i<<1;
 48         if (j+1<=tot) and (d[heap[j+1]]<d[heap[j]]) then inc(j);
 49         if d[heap[j]]>=d[heap[i]] then break;
 50         swap(heap[i],heap[j]);
 51         pl[heap[i]]:=i;
 52         pl[heap[j]]:=j;
 53         i:=j;
 54     end;
 55 end;
 56 
 57 procedure delete(x:longint);
 58 begin
 59     heap[x]:=heap[tot];
 60     dec(tot);
 61     down(x);
 62 end;
 63 
 64 procedure dij();
 65 var
 66     p,q,cur                                     :longint;
 67 begin
 68     for i:=1 to N do
 69     begin
 70         cur:=heap[1];
 71         delete(1);
 72         p:=last[cur];
 73         while p<>0 do
 74         begin
 75             q:=other[p];
 76             if d[q]>d[cur]+len[p] then
 77             begin
 78                 d[q]:=d[cur]+len[p];
 79                 up(pl[q]);
 80             end;
 81             p:=pre[p];
 82         end;
 83     end;
 84 end;
 85 
 86 begin
 87     read(N,M,S);
 88     for i:=1 to M do
 89     begin
 90         read(x,y,z);
 91         add(x,y,z);
 92     end;
 93     for i:=1 to N do d[i]:=maxlongint>>1; d[S]:=0;
 94     for i:=1 to N do heap[i]:=i;
 95     for i:=1 to N do pl[i]:=i;
 96     tot:=n;
 97     up(S);
 98     dij;
 99     for i:=1 to N do if d[i]=maxlongint>>1 then write(maxlongint,‘ ‘) else write(d[i],‘ ‘);
100 end.

 1 const mo=20000;
 2 var
 3     N,M,S,L,i,x,y,z                            :longint;
 4     pre,last,other,len                         :array[0..5000050] of longint;
 5     d,que                                     :Array[0..200050] of longint;
 6     vis                                     :array[0..100050] of boolean;
 7 
 8 procedure add(u,v,r:longint);
 9 begin
10     inc(L);
11     pre[L]:=last[u];
12     last[u]:=L;
13     other[L]:=v;
14     len[L]:=r;
15 end;
16 
17 procedure spfa();
18 var
19     p,q,cur,h,t                             :longint;
20 begin
21     for i:=1 to N do d[i]:=maxlongint>>1; d[S]:=0;
22     que[1]:=S;
23     h:=0;
24     t:=1;
25     while h<>t do
26     begin
27         h:=h mod mo+1;
28         cur:=que[h];
29         vis[cur]:=false;
30         p:=last[cur];
31         while p<>0 do
32         begin
33             q:=other[p];
34             if d[q]>d[cur]+len[p] then
35             begin
36                 d[q]:=d[cur]+len[p];
37                 if not vis[q] then
38                 begin
39                     vis[q]:=true;
40                     inc(t);
41                     que[t]:=q;
42                 end;
43             end;
44             p:=pre[p];
45         end;
46     end;
47 end;
48 
49 
50 begin
51     read(N,M,S);
52     for i:=1 to M do
53     begin
54         read(x,y,z);
55         add(x,y,z);
56     end;
57     spfa;
58     for i:=1 to N do if d[i]=maxlongint>>1 then write(maxlongint,‘ ‘) else write(d[i],‘ ‘);
59 end.

 1 var
 2     i,j,k,x,y,z                                :longint;
 3     N,M,S                                     :longint;
 4     d                                         :array[0..500,0..500] of longint;
 5 
 6 function min(x,y:longint):longint;
 7 begin
 8     if x<y then exit(x) else exit(y);
 9 end;
10 
11 begin
12     read(N,M,S);
13     for i:=1 to N do
14     for j:=1 to N do d[i,j]:=maxlongint>>1;
15     for i:=1 to N do d[i,i]:=0;
16     for i:=1 to M do
17     begin
18         read(x,y,z);
19         d[x,y]:=min(d[x,y],z);
20     end;
21     for k:=1 to N do
22     for i:=1 to N do
23     for j:=1 to N do d[i,j]:=min(d[i,j],d[i,k]+d[k,j]);
24     for i:=1 to N do write(d[S,i],‘ ‘);
25 end.