void Dijkstra(int u) { memset(vis,0,sizeof(vis)); for(int t=1;t<=n;t++) { dis[t]=map[u][t]; } vis[u]=1; for(int t=1;t<n;t++) { int minn=Inf,temp; for(int i=1;i<=n;i++) { if(!vis[i]&&dis[i]<minn) { minn=dis[i]; temp=i; } } vis[temp]=1; for(int i=1;i<=n;i++) { if(map[temp][i]+dis[temp]<dis[i]) { dis[i]=map[temp][i]+dis[temp]; } } } }
const int maxn=1e6+10; const int maxm=1e7+10; const int inf=0x3f3f3f3f; struct Dijkstra { struct Edge { int next, to ,w; } e[maxm]; int head[maxn],v[maxn],d[maxn],tol; void add(int u, int v, int w) { tol++; e[tol].to = v; e[tol].next = head[u]; e[tol].w = w; head[u] = tol; } priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >q1; int dijkstra(int s,int t) { memset(d,inf,sizeof(d)); memset(v,0,sizeof(v)); d[s] = 0; q1.push(make_pair(0, s)); while (!q1.empty()) { int x = q1.top().second; q1.pop(); if (!v[x]) { v[x] = 1; for (register int i = head[x]; i; i = e[i].next) { int to=e[i].to; if (d[to] > d[x] + e[i].w) { d[to] = d[x] + e[i].w; q1.push(make_pair(d[to], to)); } } } } return d[t]; } void init() { memset(head, 0, sizeof(head)); tol = 0; } } H;