CSU 1808：地铁（Dijkstra）

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1808

题意：……

思路：和之前的天梯赛的一题一样，但是简单点。

没办法直接用点去算。把边看成点去做，规定dis[i]为走完第i条边之后即达到edge[i].v这个点的时候需要的花费。

点数为2*m。如果用普通的Dijkstra和SPFA会超时，所以用优先队列优化的Dijkstra。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 typedef long long LL;

 const LL INF = 1000000000000000000LL;

 struct Edge {

     int u, v, nxt, w, c;

 } edge[N*];

 struct Node {

     LL d; int id;

     bool operator < (const Node &rhs) const {

         return d > rhs.d;

     }

 };

 int head[N], tot, n, m;

 bool vis[N*];

 LL dis[N*];

 void Add(int u, int v, int w, int id) {

     edge[tot] = (Edge) { u, v, head[u], w, id}; head[u] = tot++;

     edge[tot] = (Edge) { v, u, head[v], w, id}; head[v] = tot++;

 }

 LL Dijkstra() {

     for(int i = ; i < tot; i++) dis[i] = INF;

     memset(vis, , sizeof(vis));

     LL ans = INF;

     priority_queue<Node> que;

     while(!que.empty()) que.pop();

     for(int i = head[]; ~i; i = edge[i].nxt)

         que.push((Node) {edge[i].w, i}), dis[i] = edge[i].w;

     while(!que.empty()) {

         Node now = que.top(); que.pop();

         int pree = now.id; LL pred = now.d;

         if(vis[pree]) continue; vis[pree] = ;

         int u = edge[pree].v;

         if(u == n && ans > pred) ans = pred;

         for(int i = head[u]; ~i; i = edge[i].nxt) {

             int nowe = i;

             LL nowd = dis[pree] + edge[nowe].w + abs(edge[nowe].c - edge[pree].c);

             if(nowd < dis[nowe] && !vis[nowe]) {

                 dis[nowe] = nowd;

                 que.push((Node) { nowd, nowe });

             }

         }

     }

     return ans;

 }

 int main() {

     while(~scanf("%d%d", &n, &m)) {

         memset(head, -, sizeof(head)); tot = ;

         for(int i = ; i <= m; i++) {

             int u, v, c, w;

             scanf("%d%d%d%d", &u, &v, &c, &w);

             Add(u, v, w, c);

         }

         printf("%lld\n", Dijkstra());

     }

     return ;

 }

 /*

 3 3

 1 2 1 1

 2 3 2 1

 1 3 1 1

 3 3

 1 2 1 1

 2 3 2 1

 1 3 1 10

 3 2

 1 2 1 1

 2 3 1 1

 */