201712-4 行车路线

思路

拆点这种算法还是第一次见，不过能拿一点分还是可以接受吧。
主要就是说把点分为d[x][y]， x表示某个点，y表示最后一次连续的小路长度。
这样对于一个d[x][y]，如果它邻接的点对应的边是大路，那么就是d[u][0] = d[x][y] + w[i]，否则就是d[u][y + w[i]] = d[x][y] - y * y + (y + w[i]) * (y + w[i])
因为边权都为正，所以可以用迪杰斯特拉算法（SPFA算法会超时)

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N = 515;
const int M =  200010;
const int INF = 1e6;
int h[N], e[M], ne[M], w[M], f[M], idx;
bool st[N][1010];
int d[N][1010];
int n,m;
typedef struct node{
	int x,y,v;//x表示哪一个点，y表示它最后一次经过的连续的小路长度，v表示它距离源点的距离 
	bool operator < (const node& a) const {
		return v > a.v;
	}
}node;
void add(int t, int u, int v, int c){
	f[idx] = t, e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx++;
}
void dijkstra(){
	memset(d, 0x3f, sizeof(d));
	priority_queue q;
	d[1][0] = 0;
	q.push({1, 0, 0});
	while(!q.empty()){
		auto t = q.top();
		q.pop();
		if(st[t.x][t.y])continue;
		st[t.x][t.y] = true;
		for(int i = h[t.x]; i != -1;i = ne[i]){
			int x = e[i], y = t.y;
			if(f[i]){
				y += w[i];
				if(y <= 1000){
				    if(d[x][y] > t.v - t.y * t.y + y * y){
					d[x][y] = t.v - t.y * t.y + y * y;
					if(d[x][y] <= INF){
						q.push({x, y, d[x][y]});
					}
				}
				}
				
			}else{
				if(d[x][0] > t.v + w[i]){
					d[x][0] = t.v + w[i];
					if(d[x][0] <= INF){
						q.push({x, 0, d[x][0]});
					}
					
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	memset(h, -1, sizeof(h));
	while(m--){
		int t,u,v,w;
		scanf("%d%d%d%d", &t, &u, &v, &w);
		add(t, u, v, w);
		add(t, v, u, w);
	}
	dijkstra();
	int res = INF;
	for(int i = 0;i<=1000;i++)res = min(res, d[n][i]);
	cout<