差分约束系统。
偶尔发现的很好的题目，对最短路径算法的优化要求较高。
敲了一个SPFA+SLF。其中双端循环队列是手写的，int读入用了getchar处理以节省时间，作了去重边处理。但即使这样也才250ms(g++)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,hd[30000],el,eel,b[30000],d[30000]; class DQ { #define MAXL 50000 public: int a[MAXL],h,t; inline void init() { t=0; h=1; } inline void push_front(int b) { a[h++]=b; if(h==MAXL) h=0; } inline void push_back(int b) { a[t--]=b; if(t==-1) t=MAXL-1; } inline int front() { if(h==0) return a[MAXL-1]; return a[h-1]; } inline void pop_front() { if(h==0) h=MAXL-1; else h--; } inline int empty() { if(t==MAXL-1&&h==0) return 1; return t==h-1; } }dq; struct EE { int u,v,d; bool operator < (const EE &p) const { if(u<p.u) return 0; if(u>p.u) return 1; if(v<p.v) return 0; if(v>p.v) return 1; return d<p.d; } }ee[150000]; struct E { int v,d,p; }e[150000]; inline void adde(int u,int v,int d) { e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++; } inline int getint() { int d; char c; while((c=getchar())<'0'||c>'9'); d=c-'0'; while((c=getchar())>='0'&&c<='9') d=d*10+c-'0'; return d; } void init() { int i,j,k; el=eel=0; memset(hd,-1,sizeof hd); memset(b,0,sizeof b); memset(d,-1,sizeof d); dq.init(); while(m--) { i=getint(); j=getint(); k=getint(); if(i==j) continue; ee[eel].u=i-1; ee[eel].v=j-1; ee[eel].d=k; eel++; } sort(ee,ee+eel); adde(ee[0].u,ee[0].v,ee[0].d); for(i=1;i<eel;i++) { if(ee[i].u==ee[i-1].u&&ee[i].v==ee[i-1].v) continue; adde(ee[i].u,ee[i].v,ee[i].d); } } void solve() { int i,j,k,l; d[0]=0; b[0]=1; dq.push_front(0); while(!dq.empty()) { i=dq.front(); dq.pop_front(); b[i]=0; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].v; k=e[l].d; if(d[j]==-1||d[i]+k<d[j]) { d[j]=d[i]+k; if(!b[j]) { b[j]=1; if(dq.empty()||d[j]<=d[dq.front()]) dq.push_front(j); else dq.push_back(j); } } } } printf("%d\n",d[n-1]); } int main() { while(~scanf("%d%d",&n,&m)) { init(); solve(); } return 0; } |
之后又考虑了用dijkstra。没有优化过直接交果然TLE了。然后开始考虑改进。直接用最小堆来实现最优的dijkstra不太好写，而折中地每次将可能更新最短路径值的点全部push进优先队列的做法是相对比较好实现的，也不会耗损太多时间。第一次写这样的dijkstra，调试了挺久。最后在g++下235ms，c++下1297ms。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; #define maxml 30000000 int n,m,hd[30000],el,eel,b[30000],d[30000],ml; struct EE { int u,v,d; bool operator < (const EE &p) const { if(u<p.u) return 0; if(u>p.u) return 1; if(v<p.v) return 0; if(v>p.v) return 1; return d<p.d; } }ee[150000]; struct E { int v,d,p; }e[150000]; struct F { int d,i; }mem[maxml]; struct CP { bool operator ()(const F *p,const F *q) const { return p->d>q->d; } }; inline void adde(int u,int v,int d) { e[el].v=v; e[el].d=d; e[el].p=hd[u]; hd[u]=el++; } inline int getint() { int d; char c; while((c=getchar())<'0'||c>'9'); d=c-'0'; while((c=getchar())>='0'&&c<='9') d=d*10+c-'0'; return d; } void init() { int i,j,k; el=eel=ml=0; memset(hd,-1,sizeof hd); memset(b,0,sizeof b); memset(d,-1,sizeof d); while(m--) { i=getint(); j=getint(); k=getint(); if(i==j) continue; ee[eel].u=i-1; ee[eel].v=j-1; ee[eel].d=k; eel++; } sort(ee,ee+eel); adde(ee[0].u,ee[0].v,ee[0].d); for(i=1;i<eel;i++) { if(ee[i].u==ee[i-1].u&&ee[i].v==ee[i-1].v) continue; adde(ee[i].u,ee[i].v,ee[i].d); } } void solve() { int i,j,k,l; d[0]=0; b[0]=1; priority_queue<F*,vector<F*>,CP>pq; F* p; for(l=hd[0];l!=-1;l=e[l].p) { p=&mem[ml++]; d[e[l].v]=p->d=e[l].d; p->i=e[l].v; pq.push(p); } while(!b[n-1]) { while(b[i=pq.top()->i]) pq.pop(); b[i]=1; pq.pop(); for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].v; k=e[l].d; if(b[j]||d[j]!=-1&&d[i]+k>=d[j]) continue; p=&mem[ml++]; d[j]=p->d=d[i]+k; p->i=j; pq.push(p); } } printf("%d\n",d[n-1]); } int main() { while(~scanf("%d%d",&n,&m)) { init(); solve(); } return 0; } |
吐个小槽……priority_queue里面自定义仿函数时，若比较用的是<，建出来的竟然是大根堆……直觉上怎样也觉得<对应的应该是最小元素在上的小根堆才对……>__< 后记：第二天过来后被Usozki教育了下，他的代码仅仅是SPFA+栈，没有太多优化……但是直接跑出79ms进入第一版了…… 附POJ 3159 by Usozki：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<cstdio> #include<cstring> int i,j,k,s,t,d,p,dist[30005],hd[30005],el,n,m,instk[30005], inf=0x7fffffff,stk[30005],top; struct E { int v,p,d; } e[150005]; inline void adde(int u,int v,int d) { e[el].v=v,e[el].p=hd[u],e[el].d=d,hd[u]=el++; } inline int getint() { int d; char c; while((c=getchar())<'0'||c>'9'); d=c-'0'; while((c=getchar())>='0'&&c<='9') d=d*10+c-'0'; return d; } int main() { while(~scanf("%d%d",&n,&m)) { el=0,top=0; memset(dist,127,sizeof dist); memset(instk,0,sizeof instk); memset(hd,-1,sizeof hd); for(i=0; i<m; i++) { s=getint(),t=getint(),d=getint(); adde(s,t,d); } dist[1]=0; stk[++top]=1; while(top) { p=stk[top--],instk[p]=0; for(j=hd[p]; j!=-1; j=e[j].p) { k=e[j].v; if(dist[p]+e[j].d<dist[k]) { dist[k]=dist[p]+e[j].d; if(instk[k]==0)stk[++top]=k,instk[k]=1; } } } printf("%d\n",dist[n]-dist[1]); } return 0; } |