Description
Bobo 居住在大城市 ICPCCamp。
ICPCCamp 有 n 个地铁站，用 1,2,…,n 编号。 m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于 c 号线，位于站 a,b 之间，往返均需要花费 t 分钟（即从 a 到 b 需要 t 分钟，从 b 到 a 也需要 t 分钟）。
众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费 |c-c | 分钟。注意，换乘只能在地铁站内进行。
Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。
Input
输入包含不超过 20 组数据。
每组数据的第一行包含两个整数 n,m (2≤n≤10,1≤m≤10).
接下来 m 行的第 i 行包含四个整数 a,b,c,t (1≤a,b,c≤n,1≤t≤10).
保证存在从地铁站 1 到 n 的地铁线路（不一定直达）。
Output
对于每组数据，输出一个整数表示要求的值。
Sample Input
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
Sample Output
1
3
2
Hint
以边建图，通过边的权值大小进行bfs不断更新
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 100010
#define INF 0x3fffffff
typedef long long ll;
struct edge{
ll from, to, ci,w;
};
struct node{
ll x, sum;
int fa;//记录连接了几个点
friend bool operator <(node n1, node n2)
{
return n1.sum>n2.sum;
}
};
ll ans, n, m;
vector<int>G[MAXN];
vector<edge>edges;
priority_queue<node>q;
int vis[MAXN * 2];
void addedge(ll x, ll y, ll ci, ll w)
{
edge v = { x, y, ci, w };
edges.push_back(v);//边
G[x].push_back(edges.size() - 1);//点
}
void bfs()
{
node a = { 1, 0, -1 };
q.push(a);
while (!q.empty())
{
a = q.top();
q.pop();
if (a.x == n)
{
ans = a.sum;
return;
}
if (a.fa != -1 && vis[a.fa])
continue;
vis[a.fa] = 1;
for (int i = 0; i < G[a.x].size(); i++)
{
node b = a;
edge v = edges[G[a.x][i]];
b.x = v.to;
b.fa = G[a.x][i];
b.sum += v.w;
if (a.fa >= 0)
{
b.sum += abs(edges[a.fa].ci - v.ci);
}
q.push(b);
}
}
}
int main()
{
while (~scanf("%lld%lld", &n, &m))
{
for (int i = 0; i <= n; i++)
G[i].clear();
edges.clear();
for (int i = 1; i <= m; i++)
{
ll x, y, ci, w;
scanf("%lld%lld%lld%lld", &x, &y, &ci, &w);
addedge(x, y, ci, w);
addedge(y, x, ci, w);
}
ans = INF;
memset(vis, 0, sizeof(vis));
while (!q.empty())
q.pop();
bfs();
cout << ans<< endl;
}
return 0;
}
/**********************************************************************
Problem: 1808
User: leo6033
Language: C++
Result: AC
Time:1844 ms
Memory:19208 kb
**********************************************************************/