题目大意：单元最短路径（卡$SPFA$）

题解：$dijkstra$($\underline{\hspace{0.5em}}\underline{\hspace{0.5em}}gnu\underline{\hspace{0.5em}}pb\underline{\hspace{0.5em}}ds::priority\underline{\hspace{0.5em}}queue$优化)

卡点：无

 

C++ Code：

#include 
     
      #include 
      
       #define maxn 100010#define maxm 200010using namespace std;const int inf = 0x3f3f3f3f;int n, m, S;int dis[maxn];int head[maxn], cnt;struct Edge {	int to, nxt, w;} e[maxm];void add(int a, int b, int c) {	e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;}struct cmp {	inline bool operator () (const int &a, const int &b) const {		return dis[a] > dis[b];	}};__gnu_pbds::priority_queue
       
         q;__gnu_pbds::priority_queue
        
         ::point_iterator iter[maxn];void dijkstra(int S) {	for (int i = 1; i <= n; i++) dis[i] = inf, iter[i] = q.push(i);	dis[S] = 0;	q.modify(iter[S], S);	while (!q.empty()) {		int u = q.top(); q.pop();		for (int i = head[u]; i; i = e[i].nxt) {			int v = e[i].to;			if (dis[v] > dis[u] + e[i].w) {				dis[v] = dis[u] + e[i].w;				q.modify(iter[v], v);			}		}	}}int main() {	scanf("%d%d%d", &n, &m, &S);	for (int i = 0; i < m; i++) {		int a, b, c;		scanf("%d%d%d", &a, &b, &c);		add(a, b, c);	}	dijkstra(S);	for (int i = 1; i <= n; i++) {		printf("%d ", dis[i] == inf ? -1 : dis[i]);	}	puts("");	return 0;}