buaa通向女友之路~水~模板
吉大模板A的水，不知道ab同学怎么能tle的。。。。dijkstra
#include <cstdlib>
#include <limits>
#include <ctime>
#include <memory>
#include <cmath>
#include <functional>
#include <numeric>
#include <cstdio>
#include <iostream>
#include <fstream>
//#include <strstream>
#include <algorithm>
#include <iterator>
#include <map>
#include <set>
//#include <ext/hash_map>
//#include <ext/hash_set>
//#include <hash_map>
//#include <hash_set>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
using namespace std;
/*==================================================*\
| Dijkstra O(E * log E)
| INIT: 调用init(nv, ne)读入边并初始化;
| CALL: dijkstra(n, src); dist[i]为src到i的最短距离
\*==================================================*/
#define typec int // type of cost
#define V 10001
#define E 100001
const typec inf = 0x3f3f3f3f; // max of cost
typec cost[E], dist[V];
int e, pnt[E], nxt[E], head[V], prev[V], vis[V];
struct qnode {
int v;
typec c;
qnode(int vv = 0, typec cc = 0) : v(vv), c(cc) {
}
bool operator<(const qnode & r) const {
return c > r.c;
}
};
void dijkstra(int n, const int src) {
qnode mv;
int i, j, k, pre;
priority_queue<qnode> que;
vis[src] = 1;
dist[src] = 0;
que.push(qnode(src, 0));
for (pre = src, i = 1; i < n; i++) {
for (j = head[pre]; j != -1; j = nxt[j]) {
k = pnt[j];
if (vis[k] == 0 &&
dist[pre] + cost[j] < dist[k]) {
dist[k] = dist[pre] + cost[j];
que.push(qnode(pnt[j], dist[k]));
prev[k] = pre;
}
}
while (!que.empty() && vis[que.top().v] == 1)
que.pop();
if (que.empty()) break;
mv = que.top();
que.pop();
vis[pre = mv.v] = 1;
}
}
inline void addedge(int u, int v, typec c) {
pnt[e] = v;
cost[e] = c;
nxt[e] = head[u];
head[u] = e++;
}
void init(int nv, int ne) {
int i, u, v;
typec c;
e = 0;
memset(head, -1, sizeof (head));
memset(vis, 0, sizeof (vis));
memset(prev, -1, sizeof (prev));
for (i = 0; i < nv; i++) dist[i] = inf;
for (i = 0; i < ne; ++i) {
scanf("%d%d%d", &u, &v, &c); // %d: type of cost
//printf("%d%d%d\n", u, v, c);
u--;
v--;
addedge(u, v, c); // vertex: 0 ~ n-1, 单向边
//addedge(v, u, c);
}
}
int main() {
int m, n;
int s,t;
while(cin >> n >> m) {
init(n, m);
//printf("%d", e);
cin>>s>>t;
dijkstra(n, s-1);
cout << dist[t-1] << endl;
}
return 0;
}
2022年10月03日 15:06
Download the updated Canara bank RTGS/NEFT Form in PDF format. Find out Latest RTGS/NEFT form. How to fill up RTGS/NEFT form & Cheque for Canara. Enter your Canara Bank branch's name. Mention the date on which you are filling the application form. · Select between RTGS or NEFT, you can use the same.Download the updated Canara bank RTGS/NEFT Form in PDF format. Find out Latest RTGS/NEFT form. Canara Bank neft Form How to fill up RTGS/NEFT form & Cheque for Canara. Enter your Canara Bank branch's name. Mention the date on which you are filling the application form. · Select between RTGS or NEFT, you can use the same.
2023年7月31日 23:47
Puede generar rápidamente dichas copias de seguridad utilizando aka.ms/phonelinkQRC , que sincroniza directamente su teléfono inteligente con su computadora y ayuda a mantener la información sincronizada al transferir ciertas modificaciones que permite de uno a otro a través de Microsoft Phone Link. www.aka.ms La aplicación Phone Link le permite acceder a cualquier cosa en su teléfono Android desde su escritorio. Puede vincular su teléfono Android a una computadora/laptop con Windows 10/11 y permitirle ver y responder mensajes de texto de Android.
2023年8月01日 18:42
SCERT Sikkim Follows NCERT Curriculum These Textbooks are Updated as per the Syllabus Prescribed by SCERT Sikkim. Students of 3rd Class Should follow Prescribed Textbooks while Preparing for Exam.Our SCERT Sikkim 3rd Class Book 2024 Team Refer to the Respective Subject Textbook while Preparing the Final Important questions. Students Best Practice Study Materiel about Textbooks are the Fact that they are so Comprehensible that it does not require the aid of a Subject Literate.SCERT Sikkim once Publishes the Sikkim Elementary School Textbooks 2024 Other Study materials on the official web site, we will update the Information on this page.
2024年1月19日 15:56
Pavzi.com is a startup by passionate webmasters and bloggers who have a passion for providing engaging content that is accurate, interesting, and worthy to read. pavzi.com We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news. We provide you with the finest web content on every topic possible with the help of the editorial and content team.