首页 > 代码库 > LibreOJ #119. 最短路
LibreOJ #119. 最短路
二次联通门 : LibreOJ #119. 最短路
/* LibreOJ #119. 最短路 堆优化的Dijkstra */ #include <cstring> #include <cstdio> #include <queue> #define Max 6000 void read (int &now) { now = 0; register char word = getchar (); while (word < ‘0‘ || word > ‘9‘) word = getchar (); while (word >= ‘0‘ && word <= ‘9‘) { now = now * 10 + word - ‘0‘; word = getchar (); } } struct Data { int Id; int dis; bool operator < (const Data &now) const { return this->dis > now.dis; } Data (int __Id, int __dis) : Id (__Id), dis (__dis) {}; Data () {}; }; class Dijkstra_Type { private : int __to[Max << 3], __next[Max << 3]; int __dis[Max << 3]; int Edge_Count; int edge_list[Max]; bool visit[Max]; int dis[Max]; public : void Insert_edge (int from, int to, int dis) { Edge_Count ++; __to[Edge_Count] = to; __next[Edge_Count] = edge_list[from]; edge_list[from] = Edge_Count; Edge_Count ++; __to[Edge_Count] = from; __next[Edge_Count] = edge_list[to]; edge_list[to] = Edge_Count; __dis[Edge_Count] = __dis[Edge_Count - 1] = dis; } int Dijkstra (int Start, int End) { std :: priority_queue <Data> Queue; memset (dis, 0x3f, sizeof dis); Data now ; for (Queue.push (Data (Start, 0)), dis[Start] = 0; !Queue.empty (); Queue.pop ()) { now = Queue.top (); if (visit[now.Id]) continue; visit[now.Id] = true; for (int i = edge_list[now.Id]; i; i = __next[i]) if (dis[__to[i]] > dis[now.Id] + __dis[i]) { dis[__to[i]] = dis[now.Id] + __dis[i]; Queue.push (Data (__to[i], dis[__to[i]])); } } return dis[End]; } }; Dijkstra_Type Make; int main (int argc, char *argv[]) { int N, M; int x, y, z; int S, T; for (read (N), read (M), read (S), read (T); M --; ) { read (x); read (y); read (z); Make.Insert_edge (x, y, z); } printf ("%d", Make.Dijkstra (S, T)); return 0; }
LibreOJ #119. 最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。