颓废。。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn=1e5+5, maxm=1e6+5, INF=2147483647; 7 8 struct Heap_node{ 9 int value, id; 10 void reset(){ 11 value=0, id=0; 12 return; 13 } 14 }; 15 16 bool operator< (Heap_node A, Heap_node B){ 17 if (A.value>B.value) return true; 18 else return false; 19 } 20 21 class Heap{ 22 private: 23 int pos[maxn]; 24 Heap_node heap[maxn]; 25 26 void exchange(int x, int y){ 27 pos[heap[x].id]=y; 28 pos[heap[y].id]=x; 29 swap(heap[x], heap[y]); 30 } 31 32 void pushup(int now){ 33 while (now!=1&&heap[now>>1]<heap[now]){ 34 exchange(now, now>>1); 35 now>>=1; 36 } 37 return; 38 } 39 40 void pushdown(int now){ 41 bool son1, son2, flag=true; 42 while ((now<<1)<=n&&flag){ 43 flag=false; 44 son1=true, son2=true; 45 if ((now<<1|1)>n) son2=false; 46 if (son2&&heap[now<<1]<heap[now<<1|1]) son1=false; 47 else son2=false; 48 if (son1&&heap[now]<heap[now<<1]) { 49 exchange(now, now<<1); 50 now<<=1; 51 flag=true; 52 } 53 if (son2&&heap[now]<heap[now<<1|1]){ 54 exchange(now, now<<1|1); 55 now=now<<1|1; 56 flag=true; 57 } 58 } 59 return; 60 } 61 62 public: 63 int n; 64 Heap(){ 65 n=0; 66 for (int i=0; i<maxn; ++i) heap[i].reset(); 67 } 68 69 void push(int num, int id){ 70 pos[id]=++n; 71 heap[n].id=id; 72 heap[n].value=num; 73 pushup(n); 74 return; 75 } 76 77 void del(int now){ 78 pos[heap[n].id]=now; 79 pos[heap[now].id]=0; 80 heap[now]=heap[n--]; 81 pushdown(now); 82 pushup(now); // 83 } 84 85 void delid(int id){ 86 int now=pos[id]; 87 del(now); 88 return; 89 } 90 91 void modify(int value, int id){ 92 delid(id); 93 push(value, id); 94 return; 95 } 96 97 bool empty(){ 98 return !n; 99 } 100 101 Heap_node top(){ 102 return heap[1]; 103 } 104 }; 105 106 struct Edge{ 107 int to, v, next; 108 }; 109 110 struct Graph{ 111 int n, m, cntedge; 112 int fir[maxn]; 113 Edge link[maxn]; 114 Edge edge[maxm]; 115 116 void init(int nodenum, int edgenum){ 117 n=nodenum, m=edgenum; 118 } 119 120 Graph(){ 121 memset(fir, 0, sizeof(fir)); 122 memset(edge, 0, sizeof(edge)); 123 cntedge=0; 124 n=0; 125 m=0; 126 return; 127 } 128 129 void addedge(int x, int y, int v){ 130 ++cntedge; 131 edge[cntedge].to=y; 132 edge[cntedge].v=v; 133 edge[cntedge].next=fir[x]; 134 fir[x]=cntedge; 135 return; 136 } 137 138 Edge *get_link(int x){ 139 int cnt=0; 140 for (int nowedge=fir[x]; nowedge; 141 nowedge=edge[nowedge].next){ 142 link[++cnt]=edge[nowedge]; 143 } 144 link[0].v=cnt; 145 return link; 146 } 147 148 }; 149 150 int n, m, s; 151 int dis[maxn]; 152 Edge *link; 153 154 Heap h; 155 Graph g; 156 157 int main(){ 158 scanf("%d%d%d", &n, &m, &s); 159 g.init(n, m); 160 int f, gg, w; 161 for (int i=0; i<m; ++i){ 162 scanf("%d%d%d", &f, &gg, &w); 163 g.addedge(f, gg, w); 164 } 165 for (int i=1; i<=n; ++i){ 166 dis[i]=INF; 167 h.push(INF, i); 168 } 169 dis[s]=0; 170 h.modify(0, s); 171 int now, nowson, nowdis; 172 while (!h.empty()){ 173 now=h.top().id; 174 h.del(1); 175 if (dis[now]==INF) break; 176 link=g.get_link(now); 177 for (int i=1; i<=link[0].v; ++i){ //注意总共最多访问到2m条边，因此时间复杂度为mlogn 178 nowson=link[i].to; 179 nowdis=link[i].v; 180 if (dis[now]+nowdis<dis[nowson]){ 181 dis[nowson]=dis[now]+nowdis; 182 h.modify(dis[nowson], nowson); 183 } 184 } 185 } 186 for (int i=1; i<=n; ++i) 187 printf("%d ", dis[i]); 188 return 0; 189 }