ZOJ2923 Calculate Roads(SPFA의 dp)
2910 단어 SPFA
그림 dp를 배운 후 처음으로 응용한 셈이다.제목은 사실 매우 엄격하지 않다. 아무 말도 하지 않았다. 기본적으로 추측에 의존한다. 게다가 엄밀히 말하면 데이터에 인트가 폭발할 것이다. 그러나 그렇게 많든 사고방식이 맞으면 된다. - 0
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
#define maxn 5000
#define maxm 1000000
#define inf 0x3f3f3f3f
using namespace std;
vector<int> G[maxn+50];
struct Node
{
int v,k;
Node(){}
Node(int vi,int ki):v(vi),k(ki){}
};
int m,n,k;
int dis[maxn+50][55];
int num[maxn+50][55];
int vis[maxn+50][55];
int vtype[maxn];
int main()
{
while(cin>>m>>n>>k)
{
for(int i=0;i<=n;i++) G[i].clear();
int xi,yi;
for(int i=0;i<n;i++) {
scanf("%d%d",&xi,&yi);
vtype[xi]=yi;
}
for(int i=0;i<m;i++){
scanf("%d%d",&xi,&yi);
G[xi].push_back(yi);
G[yi].push_back(xi);
}
memset(dis,0x3f,sizeof(dis));
memset(num,0,sizeof(num));
queue<Node> que;
if(vtype[1]==0){
dis[1][0]=0;
num[1][0]=1;
que.push(Node(1,0));
}
else{
dis[1][1]=0;
num[1][1]=1;
que.push(Node(1,1));
}
while(!que.empty()){
Node xx=que.front();que.pop();
vis[xx.v][xx.k]=0;
int u=xx.v; int kk=xx.k;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(vtype[v]==0){
if(vis[v][kk]){
if(dis[u][kk]+1<dis[v][kk]){
dis[v][kk]=dis[u][kk]+1;
num[v][kk]=num[u][kk];
}
else if(dis[u][kk]+1==dis[v][kk]){
num[v][kk]+=num[u][kk];
}
}
else{
if(dis[u][kk]+1<dis[v][kk]){
dis[v][kk]=dis[u][kk]+1;
num[v][kk]=num[u][kk];
que.push(Node(v,kk));
vis[v][kk]=1;
}
else if(dis[u][kk]+1==dis[v][kk]){
num[v][kk]+=num[u][kk];
que.push(Node(v,kk));
vis[v][kk]=1;
}
}
}
else{
if(kk==k) continue;
if(vis[v][kk+1]){
if(dis[u][kk]+1<dis[v][kk+1]){
dis[v][kk+1]=dis[u][kk]+1;
num[v][kk+1]=num[u][kk];
}
else if(dis[u][kk]+1==dis[v][kk+1]){
num[v][kk+1]+=num[u][kk];
}
}
else{
if(dis[u][kk]+1<dis[v][kk+1]){
dis[v][kk+1]=dis[u][kk]+1;
num[v][kk+1]=num[u][kk];
que.push(Node(v,kk+1));
vis[v][kk+1]=1;
}
else if(dis[u][kk]+1==dis[v][kk+1]){
num[v][kk+1]+=num[u][kk];
que.push(Node(v,kk+1));
vis[v][kk+1]=1;
}
}
}
}
}
int mdis=inf;
for(int i=0;i<=k;i++){
mdis=min(mdis,dis[n][i]);
}
if(mdis==inf) {
puts("Impossible!");continue;
}
int ans=0;
for(int i=0;i<=k;i++){
if(dis[n][i]==mdis) ans+=num[n][i];
}
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Uva-10816-Travel in Desert하루 가까이 끊겼더니 출력 답이 거꾸로 나왔다. 방법은 w온도치를 2분 1로 매거한 다음 Spfa를 달리는 것이다 코드:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.