CSU 1808 地铁 （Dijkstra）

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;
}