Created
April 26, 2016 08:23
-
-
Save PreSoichiSumi/3238d63f51dddaee4037e93f52aee3b0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#include <X11/Intrinsic.h> | |
#include <iostream> | |
#include <string> | |
#include <cstdio> | |
#include <cmath> | |
#include <cstring> | |
#include <ctime> | |
#include <iostream> | |
#include <algorithm> | |
#include <set> | |
#include <vector> | |
#include <tuple> | |
#include <sstream> | |
#include <typeinfo> | |
#include <fstream> | |
#include <random> | |
#include <queue> | |
#include <deque> | |
#include <iterator> | |
#include <map> | |
using namespace std; | |
#define all(c) ((c).begin()), ((c).end()) | |
#define dump(c) cerr << "> " << #c << " = " << (c) << endl; | |
#define iter(c) __typeof((c).begin()) | |
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++) | |
#define REP(i, a, b) for (int i = a; i < (int)(b); i++) | |
#define rep(i, n) REP(i, 0, n) | |
#define mp make_pair | |
#define fst first | |
#define snd second | |
#define pb push_back | |
typedef unsigned int uint; | |
typedef long long ll; | |
typedef unsigned long long ull; | |
typedef vector<int> vi; | |
typedef vector<ll> vll; | |
typedef vector<vll> vvll; | |
typedef vector<vi> vvi; | |
typedef vector<double> vd; | |
typedef vector<vd> vvd; | |
typedef vector<string> vs; | |
typedef pair<int, int> pii; | |
typedef pair<ll, ll> pll; | |
//const int INF = 1 << 29; | |
const ll INF= 1LL << 60; //1はint | |
const double EPS = 1e-10; | |
template<class T> | |
bool chmax(T &a, const T &b) { | |
if (a < b) { | |
a = b; | |
return true; | |
} | |
return false; | |
} | |
template<class T> | |
bool chmin(T &a, const T &b) { | |
if (b < a) { | |
a = b; | |
return true; | |
} | |
return false; | |
} | |
template<class T> | |
ll stoi(T &str){ | |
ll ret; | |
stringstream ss; | |
ss << str; | |
ss >> ret; | |
return ret; | |
} | |
template<class T> | |
string toString(T i) { | |
stringstream ss; | |
ss << i; | |
return ss.str(); | |
} | |
struct prepare { | |
prepare() { | |
cout.setf(ios::fixed, ios::floatfield); | |
cout.precision(8); | |
ios_base::sync_with_stdio(false); | |
} | |
} _prepare; | |
//priority_queueは最小をtopに持ってくる | |
class Edge{ | |
public: | |
int to,col; | |
ll weight; | |
bool operator<(const Edge& a)const{return weight>a.weight;} | |
Edge(){}; | |
Edge(int b,int c,ll t){to=b,col=c,weight=t;} | |
}; | |
int main(){ | |
int N,M; | |
cin>>N>>M; | |
vector<vector<Edge>> graph(N); //ある点,色から伸びている辺の集合 | |
vector<map<int, ll>> dist(N); //色とそこまでの最短コスト同じkeyなら更新されるのがミソあ | |
vector<map<int, bool>> used(N); //ある点,色が使われているか | |
priority_queue<Edge> que; | |
rep(i,M){ | |
int a,b,c,t; | |
cin>>a>>b>>c>>t; | |
a--; | |
b--; | |
graph[a].pb(Edge(b,c,t)); | |
graph[b].pb(Edge(a,c,t)); | |
used[a][c]=false; //mapで[]を使ってアクセスすると要素がなかったときに新しい要素ができる | |
used[b][c]=false; | |
dist[a][c]=INF; | |
dist[b][c]=INF; | |
} | |
ll ans=INF; | |
que.push(Edge(0,1,0)); | |
dist[0][1]=true; | |
while(!que.empty()){ | |
int v=que.top().to; //pop | |
int col=que.top().col; | |
ll w=que.top().weight; | |
if(v==N-1){ | |
ans=w; | |
break; | |
} | |
que.pop(); | |
if(used[v][col])continue; //使わない | |
used[v][col]=true; //一度出した頂点は最短距離で決定.もう使わない | |
for(Edge e:graph[v]){ | |
if(dist[e.to][e.col]>w+e.weight+abs(col-e.col)){ | |
dist[e.to][e.col]=w+e.weight+abs(col-e.col); | |
que.push(Edge(e.to,e.col,dist[e.to][e.col])); | |
} | |
} | |
} | |
cout<<ans<<endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment