優先キュー最適化Dijkstraアルゴリズム
ダイレクトコード
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <ctime>
using namespace std;
#define LL long long
const int N = 30005;
const LL INF = 1LL << 60;
struct Node
{
int v,next,w;
bool operator < (const Node &a) const
{
return w > a.w;
}
}p[N],t1,t2;
bool vis[N];
int head[N],cnt;
LL dis[N];
void addedge(int u,int v,int w)
{
p[cnt].v = v;
p[cnt].next = head[u];
p[cnt].w = w;
head[u] = cnt++;
}
void Dijkstra(int s)
{
priority_queue<Node> q;
t1.v = s;
q.push(t1);
memset(vis,false,sizeof(vis));
dis[s] = 0;
while(!q.empty())
{
t1 = q.top();
q.pop();
int u = t1.v;
if(vis[u]) continue;
vis[u] = true;
for(int i = head[u]; i != -1 ; i = p[i].next)
{
int v = p[i].v;
if(!vis[v] && dis[v] > dis[u] + p[i].w)//
{
dis[v] = dis[u] + p[i].w;
t2.v = v;t2.w = dis[v];
q.push(t2);
}
}
}
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
cnt = 0;
memset(head,-1,sizeof(head));
memset(p,0,sizeof(p));
while(m--)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
int s,t;
scanf("%d %d",&s,&t);
for(int i = 1 ; i <= n ; i ++) dis[i] = INF;
Dijkstra(s);
if(dis[t] == INF) puts("-1");
else printf("%lld
",dis[t]);
}
return 0;
}