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 所需要花费的最小时间。
输入包含不超过 20 组数据。
每组数据的第一行包含两个整数 n,m (2≤n≤105,1≤m≤105).
接下来 m 行的第 i 行包含四个整数 ai,bi,ci,ti (1≤ai,bi,ci≤n,1≤ti≤109).
保证存在从地铁站 1 到 n 的地铁线路(不一定直达)。
对于每组数据,输出一个整数表示要求的值。
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
1
3
2
Dijkstra 在求最短路的时候可以 以边来求最短路,这是以前没有遇到过的。有时候图论中对点操作不正确的时候可以对边做操作
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;
const int maxn=1e5;
typedef long long int LL;
const LL INF=0x3f3f3f3f3f3f3f3f;
struct node
{
int next;
int value;
LL weight;
LL c;
}edge[maxn*2+5];
int head[maxn*2+5];
int tot;
int vis[maxn+5];
LL d[maxn*2+5];
int n,m;
void add(int x,int y,int w,int c)
{
edge[tot].value=y;
edge[tot].weight=w;
edge[tot].c=c;
edge[tot].next=head[x];
head[x]=tot++;
}
struct Node
{
int id;
LL dis;
Node(){};
Node(int id,LL dis)
{
this->id=id;
this->dis=dis;
}
friend bool operator <(Node a,Node b)
{
return a.dis>b.dis;
}
};
LL Dijkstra()
{
priority_queue<Node> q;
for(int i=0;i<tot;i++)
d[i]=INF;
LL ans=INF;
for(int i=head[1];i!=-1;i=edge[i].next)
{
d[i]=edge[i].weight;
q.push(Node(i,d[i]));
}
while(!q.empty())
{
Node term=q.top();
q.pop();
int p=edge[term.id].value;
if(p==n)
ans=min(ans,term.dis);
for(int i=head[p];i!=-1;i=edge[i].next)
{
if(d[i]>term.dis+edge[i].weight+abs(edge[i].c-edge[term.id].c))
{
d[i]=term.dis+edge[i].weight+abs(edge[i].c-edge[term.id].c);
q.push(Node(i,d[i]));
}
}
}
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int x,y,w,c;
memset(head,-1,sizeof(head));
tot=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&x,&y,&c,&w);
add(x,y,w,c);
add(y,x,w,c);
}
printf("%lld\n", Dijkstra());
}
return 0;
}