CSP 2017_12_4行车路线-白红宇

CSP 2017_12_4行车路线

阅读量：4217 次

发布时间：2019-05-26

本文共 1521 字，大约阅读时间需要 5 分钟。

题目链接：

思路：

dijkstra + 优先队列 + 记忆数组

minRoadLen[MAXN]记录每个节点连续的小路长度

dis数组记录疲劳值

这里面的需要用 long long类型存储dis

#include
   
    #include
    
     #include
     
      #define INF 0x3f3f3f3f#include
      
       #define MAXN 505#define MAXM 100005using namespace std;typedef long long ll;int n, m;struct Edge{	int to,t,w;	Edge(){}	Edge(int pt, int pto ,int pw){		t = pt;  to = pto; w = pw;	}	bool operator < (const Edge o)const{		return w > o.w;	}};ll square(ll a){	return a*a;}ll dis[MAXN];bool vis[MAXN];ll minRoadLen[MAXN];vector
       
         adj[MAXN];int dijkstra(int s)	{		priority_queue
        
          pq; for(int i = 1; i <= n; ++i){ vis[i] = false; dis[i] = INF; minRoadLen[i] = 0; } dis[s] = 0; pq.push(Edge(-1,s,0)); while(!pq.empty()){ Edge tmp = pq.top(); int cur = tmp.to; if(cur == n){ return dis[n]; } vis[cur] = true; pq.pop(); for(int i = 0; i < adj[cur].size(); ++i){ Edge e = adj[cur][i]; if(e.t == 0){//大道 if(dis[e.to] > dis[cur] + e.w){ dis[e.to] = dis[cur] + e.w; pq.push(Edge(-1,e.to,dis[e.to])); minRoadLen[e.to] = 0; } } if(e.t == 1){ ll curShortLen = minRoadLen[cur] + e.w; ll curDis = dis[cur]-square(minRoadLen[cur]) + square(curShortLen); if(curDis < dis[e.to]){ dis[e.to] = curDis; minRoadLen[e.to] = curShortLen; pq.push(Edge(-1,e.to,dis[e.to])); } } } } }int main() { int t,from,to,w; scanf("%d%d",&n,&m); for(int i = 1; i <= m; ++i){//注意 不要写成n了 scanf("%d%d%d%d",&t,&from,&to,&w); adj[from].push_back(Edge(t,to,w)); adj[to].push_back(Edge(t,from,w)); } ll ans = dijkstra(1); printf("%d\n",ans); return 0; }