学习了一下最短路的姿势，这个建图方法好妙啊，虽然不会证明正确性……
#include <bits/stdc++.h>
#define N 220000
#define INF 1000000000
using namespace std;
int n, m;
int ai[N], bi[N], ci[N], di[N];
int check;
class DIJ
{
private:
struct node {int t, d;};
struct comp {int operator () (node a, node b) {return a.d > b.d;}};
priority_queue <node, vector <node>, comp> Q;
public:
vector <int> bi[N], ci[N];
int dis[N], vis[N], pre[N];
int tot;
void build(int a, int b, int c)
{
bi[a].push_back(b); ci[a].push_back(c);
//if (check) printf("%d %d %d\n",a,b,c);
}
void solve()
{
for (int i = ; i <= tot; ++ i) dis[i] = INF, vis[i] = ;
dis[] = vis[] = ;
Q.push((node){, });
while (!Q.empty())
{
int hd;
do hd = Q.top().t, Q.pop();
while (vis[hd] && !Q.empty());
if (vis[hd]) break; else vis[hd] = ;
for (int j = ; j < bi[hd].size(); ++ j)
if (dis[hd] + ci[hd][j] < dis[bi[hd][j]])
{
dis[bi[hd][j]] = dis[hd] + ci[hd][j];
pre[bi[hd][j]] = hd == ? bi[hd][j]: pre[hd];
Q.push((node){bi[hd][j], dis[bi[hd][j]]});
}
}
}
} A, B;
int tot, ans = INF, bac = INF, pp;
int main()
{
scanf("%d%d", &n, &m); A.tot = n; B.tot = n + ;
for (int i = ; i <= m; ++ i)
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
tot ++; ai[tot] = a; bi[tot] = b; ci[tot] = c;
tot ++; ai[tot] = b; bi[tot] = a; ci[tot] = d;
A.build(a, b, c);
A.build(b, a, d);
if (a == || b == ) if (bac > c + d) bac = c + d, pp = (a == ? b: a);
}
A.solve();
A.dis[] = bac; A.pre[] = pp;
check = ;
for (int i = ; i <= tot; ++ i)
{
if (ai[i] == )
{
if (A.pre[bi[i]] != bi[i])
B.build(, bi[i], ci[i]);
}
else if (bi[i] == )
{
if (A.pre[ai[i]] != ai[i])
B.build(, n + , A.dis[ai[i]] + ci[i]);
else B.build(ai[i], n + , ci[i]);
}
else if (A.pre[ai[i]] != A.pre[bi[i]])
B.build(, bi[i], A.dis[ai[i]] + ci[i]);
else B.build(ai[i], bi[i], ci[i]);
}
B.solve();
printf("%d\n", B.dis[n + ]);
}