生活随笔
收集整理的這篇文章主要介紹了
CF449B Jzzhu and Cities（Dijkstra）
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
設(shè)每個(gè)點(diǎn)到1的距離為dis[x]dis[x]dis[x],特殊邊為(1,vi,wi)(1,v_i,w_i)(1,vi?,wi?)
1、wi>dis[vi]w_i>dis[v_i]wi?>dis[vi?]的特殊邊可以刪除
2、wi=dis[vi]且num[vi]>1w_i=dis[v_i]且num[v_i]>1wi?=dis[vi?]且num[vi?]>1,特殊邊可以刪掉
思路上的偏差：num[vi]=num[v_i]=num[vi?]= 到viv_ivi?的最短路的數(shù)量
實(shí)際：num[vi]=num[v_i]=num[vi?]= 從viv_ivi?出發(fā)有幾條邊可作為最短路的一部分
錯(cuò)因：
顯然，刪除①對(duì)是否刪除②沒(méi)有影響
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std
;
typedef long long ll
;
typedef pair
<ll
,int> pr
;
const int N
=1e5+5;
const int M
=4e5+5;
const int inf
=0x3f3f3f3f;
struct Edge{int v
,w
,nxt
;
}edge
[M
<<1];
bool vis
[N
];
ll dis
[N
];
int n
,m
,k
,head
[N
],cnt
;
int hd
[N
],ex
,nxt
[N
],val
[N
],num
[N
],ans
;
priority_queue
<pr
,vector
<pr
> ,greater
<pr
> > q
;
void add(int u
,int v
,int w
){edge
[++cnt
].v
=v
;edge
[cnt
].w
=w
;edge
[cnt
].nxt
=head
[u
];head
[u
]=cnt
;
}
void dijkstra(int s
){for(int i
=1;i
<=n
;i
++) dis
[i
]=inf
;for(int i
=1;i
<=n
;i
++) vis
[i
]=0;dis
[s
]=0;q
.push(make_pair(0,s
));while(!q
.empty()){pr tmp
=q
.top();q
.pop();int u
=tmp
.second
;if(vis
[u
]) continue;vis
[u
]=1;for(int i
=hd
[u
];i
;i
=nxt
[i
]){if(val
[i
]>dis
[u
]) ans
++;else if(val
[i
]==dis
[u
]&&num
[u
]>1){num
[u
]--;ans
++;}}for(int i
=head
[u
];i
;i
=edge
[i
].nxt
){int v
=edge
[i
].v
;int w
=edge
[i
].w
;if(dis
[v
]>dis
[u
]+1ll*w
){dis
[v
]=dis
[u
]+1ll*w
;num
[v
]=1;q
.push(pr(dis
[v
],v
));}else if(dis
[v
]==dis
[u
]+1ll*w
) num
[v
]++;}}
}
int main(){scanf("%d%d%d",&n
,&m
,&k
);int u
,v
,w
,s
,y
;for(int i
=1;i
<=m
;i
++){scanf("%d%d%d",&u
,&v
,&w
);add(u
,v
,w
);add(v
,u
,w
);}for(int i
=1;i
<=k
;i
++){scanf("%d%d",&s
,&y
);nxt
[++ex
]=hd
[s
];val
[ex
]=y
;hd
[s
]=ex
;add(1,s
,y
);add(s
,1,y
);}dijkstra(1);printf("%d\n",ans
);return 0;
}
總結(jié)
以上是生活随笔為你收集整理的CF449B Jzzhu and Cities（Dijkstra）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
