1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| void add_edge(int u,int v,int w){
to[++_]=v;
nxt[_]=frm[u];
frm[u]=_;
val[_]=w;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
int vis[N],dis[N];
void dijkstra(){
while(!Q.empty()){
int u=Q.top().second;
Q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=frm[u];i;i=nxt[i]){
if(dis[to[i]]>dis[u]+val[i]){
dis[to[i]]=dis[u]+val[i];
Q.push(make_pair(dis[to[i]],to[i]));
}
}
}
}
int main(){
for(int i=1;i<=n;i++){
dis[i]=INF;
}
dis[1]=0;
Q.push(make_pair(0,1));
dijkstra();
return 0;
}
|
