soj 1700 ping_단순

1328 단어 ping
제목 링크
제목: n변의 최단로를 구하는 무방향도를 드리겠습니다.
사고방식: 최단으로 한참을 생각했지만 생각해 내지 못했다. 경기가 끝나고 돌아가서 원래 dp로 하는 것을 보니 나의 dp는 향상되어야 한다.
sp[i][k]=min(sp[j][k-1]+dp[j][i])//k는 몇 변, j는 i
#include <iostream>
#include<cstdio>
#include<cstdio>
using namespace std;
#define INF 0xfffffff
#define MAXN 1100
#define MAXH 10
int d[MAXN][MAXN];
int sp[MAXN][MAXH+10];
int n,m,t; 
void init(){
	int i,j,a,b,c;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			d[i][j]=INF;
	for(i=0;i<n;i++)
		for(j=0;j<=MAXH;j++)
			sp[i][j]=INF;
	sp[0][0]=0;
	while(m--){
		scanf("%d%d%d",&a,&b,&c);
		if(d[a][b]>c){//    
			d[a][b]=d[b][a]=c;
		}
	}
}
int main(int argc, char** argv) {
	int i,j,k;
	while(scanf("%d%d%d",&n,&m,&t)!=EOF,n){
		init();
		for(k=1;k<=MAXH;k++)
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		if(d[j][i]<INF&&sp[j][k-1]+d[j][i]<sp[i][k]){
			sp[i][k]=sp[j][k-1]+d[j][i];//  j  i       
		}
		int ans=INF;
		for(i=0;i<=MAXH;i++)//  10   
			if(sp[t][i]<ans)
				ans=sp[t][i];
		if(ans==INF)
			printf("no
"); else printf("%d
",ans); } return 0; }

좋은 웹페이지 즐겨찾기