【Codevs 1817】灾后重建

Qizy 图论, 最短路, 解题报告

题目传送门：http://codevs.cn/problem/1817/

这题可以说是Floyd的最终考验吧？
具体来说：做了这题Floyd的原理就完全明白了吧！
详细请参考《算导》P405吧！（难得算导说了一次人话）

#include<iostream>
#include<cstdio>
#include<vector>
#define INF 1000099 
using namespace std;

struct abc{int point,len;};
int n,m;
int t[299]={0};
int f[299][299];
bool yet[299]={0};
vector<abc> path[299];  
bool day[100099]={0};
int pro=0;

void init(){
	for (int i=1;i<=250;i++){
		t[i]=INF;
	}
	for (int i=0;i<=250;i++){
	    for (int j=0;j<=250;j++){
		    f[i][j]=INF;
	    }
	}
    scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
	    scanf("%d",&t[i]); 
	    if (t[i]==0) yet[i]=true;
	}	
	abc hc;
	for (int i=1,a,b,leng;i<=m;i++){
		scanf("%d%d%d",&a,&b,&leng);
		a++;b++;
		f[a][b]=leng;f[b][a]=leng;
		hc.point=b;hc.len=leng;
		path[a].push_back(hc);
		hc.point=a;
		path[b].push_back(hc);
	}
}

void update(int num){
	int end,length;
	for (int k=pro+1;k<=end;k++)
	    yet[k]=true;
	for (int k=pro+1;k<=end;k++){
	    for (int i=1;i<=n;i++){
	    	for (int j=1;j<=n;j++){
	    		f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	    	}
	    }
	}
	pro=end; 
} 

int main(){
	int Q,x,y,ti;
	init();
	cin>>Q;
	for (int i=1;i<=Q;i++){
		scanf("%d%d%d",&x,&y,&ti);
		x++;y++;
		if (!day[ti]) {
		    update(ti);
			day[ti]=1;
		}
		if (f[x][y]<INF && yet[x] && yet[y]) printf("%d\n",f[x][y]);
		else printf("-1\n");
	}
	return 0;
}

为什么去年写的代码这么丑？ (╯‵□′)╯︵┻━┻

187 thoughts to “【Codevs 1817】灾后重建”

  15. I believe everybody went like Ones New website, reason being things like this site without doubt has a article on quality. I loved read A New content. go on To remain a useful article, I will avail Once more by One additional time. Bless you.

    Reply

  22. I’m extremely inspired with your writing talents as neatly as with the layout on your weblog.
    Is that this a paid theme or did you modify it yourself?
    Either way stay up the nice high quality writing, it’s uncommon to see
    a great blog like this one today..

    Reply

  33. I know this if off topic but I’m looking into starting my own weblog and was
    wondering what all is required to get set up?
    I’m assuming having a blog like yours would cost a pretty penny?

    I’m not very web smart so I’m not 100% certain. Any tips or advice would be greatly
    appreciated. Many thanks

    Reply

  41. Awesome blog you have here but I was wondering
    if you knew of any user discussion forums that cover the same topics talked about here?
    I’d really love to be a part of group where I can get feedback from other knowledgeable
    people that share the same interest. If you have any recommendations, please let me
    know. Thanks a lot!

    Reply

  49. I am curious to find out what blog system you have been working with?
    I’m experiencing some minor security issues with my latest site
    and I’d like to find something more safe. Do you have
    any recommendations?

    Reply

  63. I know this if off topic but I’m looking into starting my own weblog
    and was wondering what all is required to get set up?
    I’m assuming having a blog like yours would cost a pretty penny?
    I’m not very web savvy so I’m not 100% positive. Any tips
    or advice would be greatly appreciated. Thanks

    Reply

  82. Hi there! I know this is kind of off topic but I was wondering which blog platform are you using for this site?
    I’m getting sick and tired of WordPress because I’ve had issues with hackers and
    I’m looking at options for another platform.
    I would be awesome if you could point me in the direction of a good platform.

    Reply

  103. What i do not understood is actually how you are now not actually a lot more smartly-liked than you may be
    now. You are so intelligent. You realize therefore significantly relating to this topic, produced me personally
    consider it from so many numerous angles. Its like men and women aren’t interested until it’s something to do with Woman gaga!
    Your own stuffs great. At all times care for it up!

    Reply

  118. This is very interesting, You are a very skilled blogger.
    I’ve joined your rss feed and look forward to seeking more of your
    magnificent post. Also, I’ve shared your web site in my social networks!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *