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

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

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,ll> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=*1e5+;

 const int mod=1e9+;

 int n, m;

 ll ans;

 struct Edge

 {

     ll from, to, c, dist;

     Edge(ll u, ll v, ll w, ll d) :from(u), to(v), c(w), dist(d){}

 };

 struct HeapNode

 {

     ll id , val;

     HeapNode(ll x, ll y) :id(x), val(y){}

     bool operator < (const HeapNode& rhs) const{

         return val > rhs.val;

     }

 };

 struct Dijkstra

 {

     int n, m;

     vector<Edge> edges;

     vector<int> G[maxn];

     bool done[maxn];

     ll d[maxn];

     void init(int n)

     {

         this->n = n;

         for (int i = ; i < n; i++)    G[i].clear();

         edges.clear();

     }

     void AddEdges(int from, int to, int c, int dist)

     {

         edges.push_back(Edge(from,to,c,dist));

         m = edges.size();

         G[from].push_back((m - ));

     }

     void dijkstra(int s)

     {

         priority_queue<HeapNode> Q;

         for (int i = ; i<=m ; i++)    d[i] = 1e18;

         d[s] = ;

         memset(done, , sizeof(done));

         for(int i=;i<G[s].size();i++)

         {

             Edge& e=edges[G[s][i]];

             d[G[s][i]]=e.dist;

             Q.push(HeapNode(G[s][i],e.dist));

         }

         while (!Q.empty())

         {

             HeapNode x = Q.top(); Q.pop();

             int id = x.id;

             if (done[id]) continue;

             done[id] = true;

             int u=edges[id].to;

             if(u==n-)  ans=min(ans,d[id]);

             for (int i = ; i < G[u].size(); i++)

             {

                 Edge& e = edges[G[u][i]];

                 if (d[G[u][i]] > d[id] + e.dist + abs(e.c-edges[id].c))

                 {

                     d[G[u][i]] = d[id] + e.dist + abs(e.c-edges[id].c);

                     Q.push(HeapNode(G[u][i],d[G[u][i]]));

                 }

             }

         }

     }

 }t;

 int main()

 {

     //freopen("in.txt","r",stdin);

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

     {

         t.init(n);

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

         {

             int a,b,c,d;

             scanf("%d%d%d%d",&a,&b,&c,&d);

             a--; b--;

             t.AddEdges(a,b,c,d);

             t.AddEdges(b,a,c,d);

         }

         ans=1e18;

         t.dijkstra();

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

CSU 1808 地铁（最短路变形）

最新文章

热门文章