Description
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 所需要花费的最小时间。
Input
输入包含不超过 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 的地铁线路（不一定直达）。
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
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; }