CSU 1808 地铁（最短路变形）

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

题意：

Bobo 居住在大城市 ICPCCamp。

ICPCCamp 有 n 个地铁站，用 1,2,…,n 编号。 m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于 ci 号线，位于站 ai,bi 之间，往返均需要花费 ti 分钟（即从 ai 到 bi 需要 ti 分钟，从 bi 到 ai 也需要 ti 分钟）。

众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费 |ci-cj | 分钟。注意，换乘只能在地铁站内进行。

Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。

思路：
因为一个点可能位于多条边中，然后边也是有属性的，这样的话，如果记录点的状态，当前可能是最优的，但是对于后面的点来说，由于还受边的影响，就不一定是最优的。

可以自己模拟一下下面这组数据：

4 4
1 2 3 5
2 3 3 3
2 3 1 2
3 4 1 1

解决的办法有两种：一种是记录边的状态，另一种是拆点，一个点属于几条线段，就把它拆成几个点。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,ll> pll;
 15 const int INF = 0x3f3f3f3f;
 16 const int maxn=2*1e5+5;
 17 const int mod=1e9+7;
 18 
 19 int n, m;
 20 ll ans;
 21 
 22 struct Edge
 23 {
 24     ll from, to, c, dist;
 25     Edge(ll u, ll v, ll w, ll d) :from(u), to(v), c(w), dist(d){}
 26 };
 27 
 28 struct HeapNode
 29 {
 30     ll id , val;
 31     HeapNode(ll x, ll y) :id(x), val(y){}
 32     bool operator < (const HeapNode& rhs) const{
 33         return val > rhs.val;
 34     }
 35 };
 36 
 37 struct Dijkstra
 38 {
 39     int n, m;
 40     vector<Edge> edges;
 41     vector<int> G[maxn];
 42     bool done[maxn];
 43     ll d[maxn];
 44 
 45     void init(int n)
 46     {
 47         this->n = n;
 48         for (int i = 0; i < n; i++)    G[i].clear();
 49         edges.clear();
 50     }
 51 
 52     void AddEdges(int from, int to, int c, int dist)
 53     {
 54         edges.push_back(Edge(from,to,c,dist));
 55         m = edges.size();
 56         G[from].push_back((m - 1));
 57     }
 58 
 59     void dijkstra(int s)
 60     {
 61         priority_queue<HeapNode> Q;
 62         for (int i = 0; i<=m ; i++)    d[i] = 1e18;
 63         d[s] = 0;
 64         memset(done, 0, sizeof(done));
 65         for(int i=0;i<G[s].size();i++)
 66         {
 67             Edge& e=edges[G[s][i]];
 68             d[G[s][i]]=e.dist;
 69             Q.push(HeapNode(G[s][i],e.dist));
 70         }
 71         while (!Q.empty())
 72         {
 73             HeapNode x = Q.top(); Q.pop();
 74             int id = x.id;
 75             if (done[id]) continue;
 76             done[id] = true;
 77             int u=edges[id].to;
 78             if(u==n-1)  ans=min(ans,d[id]);
 79 
 80             for (int i = 0; i < G[u].size(); i++)
 81             {
 82                 Edge& e = edges[G[u][i]];
 83                 if (d[G[u][i]] > d[id] + e.dist + abs(e.c-edges[id].c))
 84                 {
 85                     d[G[u][i]] = d[id] + e.dist + abs(e.c-edges[id].c);
 86                     Q.push(HeapNode(G[u][i],d[G[u][i]]));
 87                 }
 88             }
 89         }
 90     }
 91 }t;
 92 
 93 
 94 int main()
 95 {
 96     //freopen("in.txt","r",stdin);
 97     while(~scanf("%d%d",&n,&m))
 98     {
 99         t.init(n);
100         for(int i=0;i<m;i++)
101         {
102             int a,b,c,d;
103             scanf("%d%d%d%d",&a,&b,&c,&d);
104             a--; b--;
105             t.AddEdges(a,b,c,d);
106             t.AddEdges(b,a,c,d);
107         }
108         ans=1e18;
109         t.dijkstra(0);
110         cout<<ans<<endl;
111     }
112     return 0;
113 }