1343 運輸線（最短路）

描述： 某次校賽，倒數第二難的題（按AC人數來看）。

沒轉過腦筋來看的話，确實有點無從下手。之後問了一個很巨的的高一OIer女孩，

她把案例給我比劃了下，讓我跑個最短路就好，我想了想，好像還真是這麼回事。（Orz,不虧是北大冬令營選手）= =

感覺沒她提示，我怎麼也想不到是最短路啊。同時也問了快畢業的lx學長，雖然他已經記不得題意，但從他的code裡分析就是如此。

#include <iostream>    
#include <algorithm>    
#include <vector>    
#include <queue>    
#include <cstring>   
using namespace std;     
#define mp make_pair    
#define pb push_back    
#define fi first    
#define se second    
#define rep(i,a,n) for(int i=a;i<n;i++)    
#define sz(a) (int)(a).size() 
typedef pair<int,int> PII; 
const int maxn = 1e3+10;     
const int INF = 0x3f3f3f3f;    
// head      
  
int w,h,n;    
int d[maxn];      
vector<PII> E[maxn];         
struct pos {     
    int x1, y1, x2, y2;    
    pos(int _x1=0,int _y1=0,int _x2=0,int _y2=0):x1(_x1),y1(_y1),x2(_x2),y2(_y2){}    
    void read() {cin >> x1 >> y1 >> x2 >> y2;}     
}p[maxn];    
    
void solve(int s, int t) {    
    memset(d, INF, sizeof(d));      
    d[0] = 0;      
    priority_queue<PII> q;      
    q.push(mp(-d[s], s));        
    while(!q.empty()) {      
        int now = q.top().se;     
        if(now == t) return;    
        q.pop();      
        rep(i, 0 ,sz(E[now])) {      
            int next = E[now][i].fi;      
            if(d[next] > d[now] + E[now][i].se) {      
                d[next] = d[now] + E[now][i].se;      
                q.push(mp(-d[next], next));      
            }       
        }      
    }      
}      
int value(pos a,pos b) {     
     if(a.x1 > b.x1)  swap(a, b);     
     if(a.x2 >= b.x1)        
        return min(abs(b.y1-a.y2), abs(a.y1-b.y2)) - 1;     
     if((a.y2 >= b.y1 && a.y2 <= b.y2) || (a.y1 <= b.y2 && a.y2 >= b.y2))     
       return b.x1 - a.x2 - 1;    
      int tem = min(abs(b.y1 - a.y2), abs(a.y1 - b.y2));  
      return max(tem, b.x1 - a.x2) - 1;     
 }  
    
 int main(void) {     
    cin >> w >> h >> n;     
    for(int i = 1; i <= n; i++) {    
        p[i].read();    
    }    
    p[0] = pos(-1, -1, -1, INF);    
    p[n + 1] = pos(w, -1, w, INF);    
     for(int i = 0; i <= n + 1; i++)     
         for(int j = 0; j < i; j++) {    
                int v = value(p[i], p[j]);    
                E[i].pb(mp(j, v));    
                E[j].pb(mp(i, v));    
         }    
    solve(0, n + 1);    
    cout << d[n + 1] << endl;     
    return 0;    
}