锘??xml version="1.0" encoding="utf-8" standalone="yes"?>久久精品成人欧美大片,久久久艹,日本欧美久久久久免费播放网http://www.shnenglu.com/cucumber/cucumberzh-cnSun, 11 May 2025 23:14:59 GMTSun, 11 May 2025 23:14:59 GMT60poj3259 WormHoles Spfa || BellmanFordhttp://www.shnenglu.com/cucumber/archive/2011/07/06/150263.htmlcucumbercucumberTue, 05 Jul 2011 17:20:00 GMThttp://www.shnenglu.com/cucumber/archive/2011/07/06/150263.htmlhttp://www.shnenglu.com/cucumber/comments/150263.htmlhttp://www.shnenglu.com/cucumber/archive/2011/07/06/150263.html#Feedback0http://www.shnenglu.com/cucumber/comments/commentRss/150263.htmlhttp://www.shnenglu.com/cucumber/services/trackbacks/150263.html

#include聽(tīng)<cstdio>
#include聽(tīng)<cstdlib>
#include聽(tīng)<queue>
#include聽(tīng)<deque>
using聽(tīng)namespace聽(tīng)std;

struct聽(tīng)Node聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)to;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)weight;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)Node聽(tīng)*next;
};

#define聽(tīng)MAXFIELD聽(tīng)(1000聽(tīng)+聽(tīng)10)
#define聽(tīng)MAXPATH聽(tīng)(2500聽(tīng)+聽(tīng)10)
#define聽(tīng)MAXWORMHOLE聽(tīng)(200聽(tīng)+聽(tīng)10)
Node聽(tīng)nodeHead[MAXFIELD];
Node聽(tīng)nodes[MAXPATH聽(tīng)*聽(tīng)2聽(tīng)+聽(tīng)MAXWORMHOLE];
int聽(tīng)dis[MAXFIELD聽(tīng)+聽(tīng)1];
bool聽(tīng)isInQueue[MAXFIELD聽(tīng)+聽(tīng)1];
int聽(tīng)allocPos聽(tīng)=聽(tīng)0;
Node聽(tīng)*getNode()聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)return聽(tīng)nodes聽(tīng)+聽(tīng)allocPos++;
}
void聽(tīng)initGraph(int聽(tīng)n)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)allocPos聽(tīng)=聽(tīng)0;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)i聽(tīng)=聽(tīng)0;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)for聽(tīng)(i聽(tīng)=聽(tīng)0;聽(tīng)i聽(tīng)<聽(tīng)n;聽(tīng)++i)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)nodeHead[i].next聽(tīng)=聽(tīng)NULL;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)dis[i]聽(tīng)=聽(tīng)0;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
}
void聽(tīng)addEdge(int聽(tīng)from,聽(tīng)int聽(tīng)to,聽(tīng)int聽(tīng)timeNeed)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)Node聽(tīng)*newNode聽(tīng)=聽(tīng)getNode();
聽(tīng)聽(tīng)聽(tīng)聽(tīng)newNode->next聽(tīng)=聽(tīng)nodeHead[from].next;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)newNode->to聽(tīng)=聽(tīng)to;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)newNode->weight聽(tīng)=聽(tīng)timeNeed;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)nodeHead[from].next聽(tīng)=聽(tīng)newNode;
}

int聽(tīng)main()聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)caseCount,聽(tīng)fieldCount,聽(tīng)pathCount,聽(tīng)wormHoleCount;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)i,聽(tīng)j,聽(tīng)from,聽(tīng)to,聽(tīng)timeNeed;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)scanf("%d",聽(tīng)&caseCount);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)for聽(tīng)(i聽(tīng)=聽(tīng)0;聽(tīng)i聽(tīng)<聽(tīng)caseCount;聽(tīng)i++)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)scanf("%d%d%d",聽(tīng)&fieldCount,聽(tīng)&pathCount,聽(tīng)&wormHoleCount);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)initGraph(fieldCount聽(tīng)+聽(tīng)1);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)for聽(tīng)(j聽(tīng)=聽(tīng)0;聽(tīng)j聽(tīng)<聽(tīng)pathCount;聽(tīng)j++)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)scanf("%d%d%d",聽(tīng)&from,聽(tīng)&to,聽(tīng)&timeNeed);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)addEdge(from,聽(tīng)to,聽(tīng)timeNeed);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)addEdge(to,聽(tīng)from,聽(tīng)timeNeed);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)for聽(tīng)(j聽(tīng)=聽(tīng)0;聽(tīng)j聽(tīng)<聽(tīng)wormHoleCount;聽(tīng)++j)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)scanf("%d%d%d",聽(tīng)&from,聽(tīng)&to,聽(tīng)&timeNeed);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)addEdge(from,聽(tīng)to,聽(tīng)-timeNeed);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}

聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)//聽(tīng)鍏抽敭:聽(tīng)鎸夌収棰樼洰鐨勮姹?聽(tīng)鍙互鐪嬪嚭鏄壘鍥句腑鏈夋病鏈夎礋鐜?br />聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)//聽(tīng)寮曞叆涓涓秴綰х偣s,聽(tīng)s鑳藉鍒拌揪浠繪剰涓涓猣ield,聽(tīng)浣嗘槸娌℃湁浠諱綍field鑳藉鍒拌揪s
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)//聽(tīng)鐒跺悗濡傛灉鍥句腑涓嶅瓨鍦ㄨ礋鐜?聽(tīng)鍒欏湪緇忚繃fieldCount嬈℃澗寮?鎴戝彨浼樺寲)浠ュ悗,聽(tīng)
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)//聽(tīng)灝辨病鏈夊姙娉曚嬌浠繪剰涓涓猣ield鑺傜偣鐨勬潈鍊煎彉灝忎簡(jiǎn),聽(tīng)鑰屽鏋滃瓨鍦ㄨ礋鐜?聽(tīng)
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)//聽(tīng)鍒欒繕鑳芥澗寮?浼樺寲.
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)//聽(tīng)榪欏氨鏄負(fù)浠涔堝垵濮嬪寲鏃墮渶瑕佹妸鎵鏈夌殑field閮藉帇鍏ラ槦鍒?
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)deque<int>聽(tīng)q;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)for聽(tīng)(j聽(tīng)=聽(tīng)1;聽(tīng)j聽(tīng)<=聽(tīng)fieldCount;聽(tīng)++j)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)q.push_back(j);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)isInQueue[j]聽(tīng)=聽(tīng)true;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)bool聽(tīng)answer聽(tīng)=聽(tīng)false;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)round聽(tīng)=聽(tīng)0;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)while聽(tīng)(!q.empty())聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)n聽(tīng)=聽(tīng)q.size();
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)for聽(tīng)(j聽(tīng)=聽(tīng)0;聽(tīng)j聽(tīng)<聽(tīng)n;聽(tīng)j++)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)u聽(tīng)=聽(tīng)q.front();
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)q.pop_front();
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)isInQueue[u]聽(tīng)=聽(tīng)false;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)Node聽(tīng)*tra;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)for聽(tīng)(tra聽(tīng)=聽(tīng)nodeHead[u].next;聽(tīng)tra聽(tīng)!=聽(tīng)NULL;聽(tīng)tra聽(tīng)=聽(tīng)tra->next)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)int聽(tīng)temp聽(tīng)=聽(tīng)tra->weight聽(tīng)+聽(tīng)dis[u];
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)if聽(tīng)(temp聽(tīng)<聽(tīng)dis[tra->to])聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)dis[tra->to]聽(tīng)=聽(tīng)temp;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)if聽(tīng)(!isInQueue[tra->to])聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)q.push_back(tra->to);
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)isInQueue[tra->to]聽(tīng)=聽(tīng)true;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)round++;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)if聽(tīng)(round聽(tīng)>聽(tīng)fieldCount)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)answer聽(tīng)=聽(tīng)true;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)q.clear();
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)break;
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}

聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)if聽(tīng)(answer)聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)puts("YES");
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)else聽(tīng){
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)puts("NO");
聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)聽(tīng)}
聽(tīng)聽(tīng)聽(tīng)聽(tīng)}

聽(tīng)聽(tīng)聽(tīng)聽(tīng)return聽(tīng)0;
}


cucumber 2011-07-06 01:20 鍙戣〃璇勮
]]>poj1062 鏄傝吹鐨勫紺?/title><link>http://www.shnenglu.com/cucumber/archive/2011/07/06/150262.html</link><dc:creator>cucumber</dc:creator><author>cucumber</author><pubDate>Tue, 05 Jul 2011 16:58:00 GMT</pubDate><guid>http://www.shnenglu.com/cucumber/archive/2011/07/06/150262.html</guid><wfw:comment>http://www.shnenglu.com/cucumber/comments/150262.html</wfw:comment><comments>http://www.shnenglu.com/cucumber/archive/2011/07/06/150262.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/cucumber/comments/commentRss/150262.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/cucumber/services/trackbacks/150262.html</trackback:ping><description><![CDATA[Dijkstra 鏈紭鍖栫増, 綆楁硶鐩稿娓呮櫚:<br /><br /> <div style="border-bottom: #cccccc 1px solid; border-left: #cccccc 1px solid; padding-bottom: 4px; background-color: #eeeeee; padding-left: 4px; width: 98%; padding-right: 5px; font-size: 13px; word-break: break-all; border-top: #cccccc 1px solid; border-right: #cccccc 1px solid; padding-top: 4px"><!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />--><span style="color: #008000">//</span><span style="color: #008000"> 鍏抽敭1: 澶勭悊姣忎釜浜虹殑鍦頒綅絳夌駭<br /></span><span style="color: #008000">//</span><span style="color: #008000"> 鍔炴硶: 鏋氫婦--鍋囪鏌愮鏂規(guī)鏄渶鐪侀挶鐨? <br /></span><span style="color: #008000">//</span><span style="color: #008000"> 鍒欒鏂規(guī)涓殑鎵鏈変氦鏄撹呯殑鍦頒綅絳夌駭閮戒細(xì)钀藉湪涓涓搴︿負(fù)rankLimit鐨勫尯闂?br /></span><span style="color: #008000">//</span><span style="color: #008000"> 浜庢槸鍙互鏋氫婦榪欎釜鍖洪棿: <br /></span><span style="color: #008000">//</span><span style="color: #008000"> [ownerRank[1] - rankLimit, ownerRank] ~ [ownerRank[1], ownerRank + rankLimit]<br /></span><span style="color: #008000">//</span><span style="color: #008000"> 浜庢槸榪欓亾棰樿冨療浜?jiǎn)鏈鐭礬鐨刣ijkstra綆楁硶涓庢灇涓劇殑緇撳悎.<br /></span><span style="color: #008000">//</span><span style="color: #008000"><br /></span><span style="color: #008000">//</span><span style="color: #008000"> 鍏朵腑鏋氫婦鍙鏄渶瑕佽冨療鍏跺鏉傚害鐨? <br /></span><span style="color: #008000">//</span><span style="color: #008000"> dijkstra綆楁硶鐨勫鏉傚害涓? O(n * n), n涓鴻妭鐐規(guī)暟鐩?br /></span><span style="color: #008000">//</span><span style="color: #008000"> 鏋氫婦閲忎負(fù) rankLimit + 1;<br /></span><span style="color: #008000">//</span><span style="color: #008000"> 浜庢槸鏋氫婦 + dijkstra鐨勭畻娉曞鏉傚害涓?nbsp;O(n * n) * (rankLimit + 1)<br /><br /><br /></span><span style="color: #008000">//</span><span style="color: #008000"> 鍏抽敭2: 鐢遍鎰忚鑱旀兂鍒扮敤鏈鐭礬, 鑰屼笖鏄竟鏉冧負(fù)姝ｇ殑鏈鐭礬<br /></span><span style="color: #008000">//</span><span style="color: #008000"> 1) 浠ョ墿鍝佷負(fù)鍥捐妭鐐?br /></span><span style="color: #008000">//</span><span style="color: #008000"> 2) 璁緄鐗╁搧濡傛灉鑳界敤j鐗╁搧浠ヤ環(huán)鏍糾浜ゆ崲, 鍒欒竟(i,j)鐨勬潈鍊間負(fù)m<br /></span><span style="color: #008000">//</span><span style="color: #008000"> 3) 璁炬眰寰楄妭鐐?鍒扮墿鍝亁鐨勬渶鐭礬, 璇ユ渶鐭礬鐨勬潈鍊煎拰涓簍w(total weight鐨勭緝鍐?, <br /></span><span style="color: #008000">//</span><span style="color: #008000">    鍒欎粠鐗╁搧x寮濮嬬墿鐗╀氦鎹㈢殑鎵鏈夋柟妗堜腑, 鏈鑺傜渷鐨勬柟妗堜細(xì)鑰楄垂tw + price[x]鐨勯噾閽?br /></span><span style="color: #008000">//</span><span style="color: #008000">    鑰屽紺兼渶灝戦渶瑕佺殑閲戝竵鏁板氨鏄墍鏈?nbsp;1 <= x <= goodsCount 涓? <br /></span><span style="color: #008000">//</span><span style="color: #008000">    tw[1][x] + price[x]鏈灝忕殑閭ｄ釜. (tw[1][x]琛ㄧず1鍒皒鐨勬渶鐭礬寰勬潈鍊?<br /><br /><br /></span><span style="color: #008000">//</span><span style="color: #008000"> 浼樺寲1: 鍦╠ijkstra綆楁硶鐨勪唬鐮侀儴鍒? 闇瑕佸鍘熺偣鍒拌妭鐐圭殑鏈灝忚窛紱繪槸鍚﹀凡鐭ヤ綔鍑哄垽鏂?<br /></span><span style="color: #008000">//</span><span style="color: #008000"> 榪欎釜鍒ゆ柇鏄敤bool鏁扮粍disKnown鏉ュ垽鏂殑, 嫻垂澶ч噺鏃墮棿.<br /></span><span style="color: #008000">//</span><span style="color: #008000"> 鍙互浼樺寲涓烘坊鍔犱竴涓暟緇? 鐢ㄨ鏁扮粍淇濆瓨鏈灝忚窛紱繪湭鐭ョ殑鑺傜偣鐨勭紪鍙? <br /></span><span style="color: #008000">//</span><span style="color: #008000"> 鍙鐞嗘暟緇勪腑鐨勮妭鐐?</span><span style="color: #008000"><br /></span><span style="color: #000000">#include </span><span style="color: #000000"><</span><span style="color: #000000">cstdio</span><span style="color: #000000">></span><span style="color: #000000"><br /></span><span style="color: #0000ff">using</span><span style="color: #000000"> </span><span style="color: #0000ff">namespace</span><span style="color: #000000"> std;<br /><br /></span><span style="color: #0000ff">struct</span><span style="color: #000000"> Node {<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> to;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> weight;<br />    Node </span><span style="color: #000000">*</span><span style="color: #000000">next;<br />};<br /><br /></span><span style="color: #0000ff">#define</span><span style="color: #000000"> INF (1 << 30)</span><span style="color: #000000"><br /></span><span style="color: #0000ff">#define</span><span style="color: #000000"> MAXNODE (100 + 10)</span><span style="color: #000000"><br /></span><span style="color: #0000ff">#define</span><span style="color: #000000"> MAXEDGE (MAXNODE * MAXNODE + 10)</span><span style="color: #000000"><br />Node nodeHead[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br />Node nodes[MAXEDGE];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> ownerRank[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> price[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> minWeight[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /></span><span style="color: #0000ff">bool</span><span style="color: #000000"> disKnown[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /><br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> allocPos </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />Node </span><span style="color: #000000">*</span><span style="color: #000000">getNode() {<br />    </span><span style="color: #0000ff">return</span><span style="color: #000000"> nodes </span><span style="color: #000000">+</span><span style="color: #000000"> allocPos</span><span style="color: #000000">++</span><span style="color: #000000">;<br />}<br /></span><span style="color: #0000ff">void</span><span style="color: #000000"> initGraph(</span><span style="color: #0000ff">int</span><span style="color: #000000"> n) {<br />    allocPos </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />    </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">; i </span><span style="color: #000000"><</span><span style="color: #000000"> n; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />        nodeHead[i].next </span><span style="color: #000000">=</span><span style="color: #000000"> NULL;<br />        minWeight[i] </span><span style="color: #000000">=</span><span style="color: #000000"> INF;<br />    }<br />}<br /></span><span style="color: #0000ff">void</span><span style="color: #000000"> addEdge(</span><span style="color: #0000ff">int</span><span style="color: #000000"> from, </span><span style="color: #0000ff">int</span><span style="color: #000000"> to, </span><span style="color: #0000ff">int</span><span style="color: #000000"> weight) {<br />    Node </span><span style="color: #000000">*</span><span style="color: #000000">newNode </span><span style="color: #000000">=</span><span style="color: #000000"> getNode();<br />    newNode</span><span style="color: #000000">-></span><span style="color: #000000">next </span><span style="color: #000000">=</span><span style="color: #000000"> nodeHead[from].next;<br />    newNode</span><span style="color: #000000">-></span><span style="color: #000000">to </span><span style="color: #000000">=</span><span style="color: #000000"> to;<br />    newNode</span><span style="color: #000000">-></span><span style="color: #000000">weight </span><span style="color: #000000">=</span><span style="color: #000000"> weight;<br />    nodeHead[from].next </span><span style="color: #000000">=</span><span style="color: #000000"> newNode;<br />}<br /><br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> main() {<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> rankLimit, goodsCount, substituteCount, subPrice, num, minPrice, minWei;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> minWeiPos;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> i, j, rankStart;<br />    scanf(</span><span style="color: #000000">"</span><span style="color: #000000">%d%d</span><span style="color: #000000">"</span><span style="color: #000000">, </span><span style="color: #000000">&</span><span style="color: #000000">rankLimit, </span><span style="color: #000000">&</span><span style="color: #000000">goodsCount);<br />    initGraph(goodsCount </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">);<br />    </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">; i </span><span style="color: #000000"><=</span><span style="color: #000000"> goodsCount; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />        scanf(</span><span style="color: #000000">"</span><span style="color: #000000">%d%d%d</span><span style="color: #000000">"</span><span style="color: #000000">, price </span><span style="color: #000000">+</span><span style="color: #000000"> i, ownerRank </span><span style="color: #000000">+</span><span style="color: #000000"> i, </span><span style="color: #000000">&</span><span style="color: #000000">substituteCount);<br />        </span><span style="color: #0000ff">for</span><span style="color: #000000"> (j </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">; j </span><span style="color: #000000"><</span><span style="color: #000000"> substituteCount; </span><span style="color: #000000">++</span><span style="color: #000000">j) {<br />            scanf(</span><span style="color: #000000">"</span><span style="color: #000000">%d%d</span><span style="color: #000000">"</span><span style="color: #000000">, </span><span style="color: #000000">&</span><span style="color: #000000">num, </span><span style="color: #000000">&</span><span style="color: #000000">subPrice);<br />            addEdge(i, num, subPrice);<br />        }<br />    }<br />    <br />    minPrice </span><span style="color: #000000">=</span><span style="color: #000000"> price[</span><span style="color: #000000">1</span><span style="color: #000000">];<br />    </span><span style="color: #0000ff">for</span><span style="color: #000000"> (rankStart </span><span style="color: #000000">=</span><span style="color: #000000"> ownerRank[</span><span style="color: #000000">1</span><span style="color: #000000">] </span><span style="color: #000000">-</span><span style="color: #000000"> rankLimit; rankStart </span><span style="color: #000000"><=</span><span style="color: #000000"> ownerRank[</span><span style="color: #000000">1</span><span style="color: #000000">]; rankStart</span><span style="color: #000000">++</span><span style="color: #000000">) {<br />        </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">; i </span><span style="color: #000000"><=</span><span style="color: #000000"> goodsCount; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />            minWeight[i] </span><span style="color: #000000">=</span><span style="color: #000000"> INF;<br />            // 濡傛灉鏌愪釜鑺傜偣/鍟嗗搧鎷ユ湁鑰呯殑闃剁駭鍦頒綅涓嶅湪[rankStart, rankStart + rankLimit]<br />            // 鐨勮寖鍥村唴, 灝變笉蹇呰冭檻璇ヨ妭鐐?br />            </span><span style="color: #0000ff">if</span><span style="color: #000000"> (ownerRank[i] </span><span style="color: #000000"><</span><span style="color: #000000"> rankStart </span><span style="color: #000000">||</span><span style="color: #000000"> ownerRank[i] </span><span style="color: #000000">></span><span style="color: #000000"> rankStart </span><span style="color: #000000">+</span><span style="color: #000000"> rankLimit) {<br />                disKnown[i] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">true</span><span style="color: #000000">;<br />            }<br />            </span><span style="color: #0000ff">else</span><span style="color: #000000"> {<br />                disKnown[i] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">false</span><span style="color: #000000">;<br />            }<br />        }<br /><br />        disKnown[</span><span style="color: #000000">1</span><span style="color: #000000">] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">false</span><span style="color: #000000">;<br />        minWeight[</span><span style="color: #000000">1</span><span style="color: #000000">] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />        </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">; i </span><span style="color: #000000"><=</span><span style="color: #000000"> goodsCount; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />            minWei </span><span style="color: #000000">=</span><span style="color: #000000"> INF;<br />            </span><span style="color: #0000ff">for</span><span style="color: #000000"> (j </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">; j </span><span style="color: #000000"><=</span><span style="color: #000000"> goodsCount; </span><span style="color: #000000">++</span><span style="color: #000000">j) {<br />                </span><span style="color: #0000ff">if</span><span style="color: #000000"> (</span><span style="color: #000000">!</span><span style="color: #000000">disKnown[j] </span><span style="color: #000000">&&</span><span style="color: #000000"> minWeight[j] </span><span style="color: #000000"><</span><span style="color: #000000"> minWei) {<br />                    minWei </span><span style="color: #000000">=</span><span style="color: #000000"> minWeight[j];<br />                    minWeiPos </span><span style="color: #000000">=</span><span style="color: #000000"> j;<br />                }<br />            }<br />            disKnown[minWeiPos] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">true</span><span style="color: #000000">;<br />            </span><span style="color: #0000ff">if</span><span style="color: #000000"> (minWei </span><span style="color: #000000">+</span><span style="color: #000000"> price[minWeiPos] </span><span style="color: #000000"><</span><span style="color: #000000"> minPrice) {<br />                minPrice </span><span style="color: #000000">=</span><span style="color: #000000"> minWei </span><span style="color: #000000">+</span><span style="color: #000000"> price[minWeiPos];<br />            }<br />            </span><span style="color: #0000ff">for</span><span style="color: #000000"> (Node </span><span style="color: #000000">*</span><span style="color: #000000">tra </span><span style="color: #000000">=</span><span style="color: #000000"> nodeHead[minWeiPos].next; tra </span><span style="color: #000000">!=</span><span style="color: #000000"> NULL; tra </span><span style="color: #000000">=</span><span style="color: #000000"> tra</span><span style="color: #000000">-></span><span style="color: #000000">next) {<br />                </span><span style="color: #0000ff">if</span><span style="color: #000000"> (</span><span style="color: #000000">!</span><span style="color: #000000">disKnown[tra</span><span style="color: #000000">-></span><span style="color: #000000">to] </span><span style="color: #000000">&&</span><span style="color: #000000"> <br />                        minWeight[tra</span><span style="color: #000000">-></span><span style="color: #000000">to] </span><span style="color: #000000">></span><span style="color: #000000"> minWeight[minWeiPos] </span><span style="color: #000000">+</span><span style="color: #000000"> tra</span><span style="color: #000000">-></span><span style="color: #000000">weight ) {<br />                    minWeight[tra</span><span style="color: #000000">-></span><span style="color: #000000">to] </span><span style="color: #000000">=</span><span style="color: #000000"> minWeight[minWeiPos] </span><span style="color: #000000">+</span><span style="color: #000000"> tra</span><span style="color: #000000">-></span><span style="color: #000000">weight;<br />                }<br />            }<br />        }<br />    }<br />    printf(</span><span style="color: #000000">"</span><span style="color: #000000">%d\n</span><span style="color: #000000">"</span><span style="color: #000000">, minPrice);<br /><br />    </span><span style="color: #0000ff">return</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />}</span></div><br /><br /><br />浼樺寲鍚? 閫熷害瑕佸揩涓浜? 浣嗘槸浠ｇ爜姣旇緝闅劇湅, 瀵瑰彉閲忕殑鍛藉悕璁╀漢姣旇緝鎭肩伀:<br /><br /> <div style="border-bottom: #cccccc 1px solid; border-left: #cccccc 1px solid; padding-bottom: 4px; background-color: #eeeeee; padding-left: 4px; width: 98%; padding-right: 5px; font-size: 13px; word-break: break-all; border-top: #cccccc 1px solid; border-right: #cccccc 1px solid; padding-top: 4px"><!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />--><span style="color: #000000">#include </span><span style="color: #000000"><</span><span style="color: #000000">cstdio</span><span style="color: #000000">></span><span style="color: #000000"><br /></span><span style="color: #0000ff">using</span><span style="color: #000000"> </span><span style="color: #0000ff">namespace</span><span style="color: #000000"> std;<br /><br /></span><span style="color: #0000ff">struct</span><span style="color: #000000"> Node {<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> to;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> weight;<br />    Node </span><span style="color: #000000">*</span><span style="color: #000000">next;<br />};<br /><br /></span><span style="color: #0000ff">#define</span><span style="color: #000000"> INF (1 << 30)</span><span style="color: #000000"><br /></span><span style="color: #0000ff">#define</span><span style="color: #000000"> MAXNODE (100 + 10)</span><span style="color: #000000"><br /></span><span style="color: #0000ff">#define</span><span style="color: #000000"> MAXEDGE (MAXNODE * MAXNODE + 10)</span><span style="color: #000000"><br />Node nodeHead[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br />Node nodes[MAXEDGE];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> ownerRank[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> price[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> minWeight[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> distanceUnknown[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> distanceUnknownCount;<br /></span><span style="color: #0000ff">bool</span><span style="color: #000000"> isDistanceKnown[MAXNODE </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">];<br /><br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> allocPos </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />Node </span><span style="color: #000000">*</span><span style="color: #000000">getNode() {<br />    </span><span style="color: #0000ff">return</span><span style="color: #000000"> nodes </span><span style="color: #000000">+</span><span style="color: #000000"> allocPos</span><span style="color: #000000">++</span><span style="color: #000000">;<br />}<br /></span><span style="color: #0000ff">void</span><span style="color: #000000"> initGraph(</span><span style="color: #0000ff">int</span><span style="color: #000000"> n) {<br />    allocPos </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />    </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">; i </span><span style="color: #000000"><</span><span style="color: #000000"> n; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />        nodeHead[i].next </span><span style="color: #000000">=</span><span style="color: #000000"> NULL;<br />        minWeight[i] </span><span style="color: #000000">=</span><span style="color: #000000"> INF;<br />    }<br />}<br /></span><span style="color: #0000ff">void</span><span style="color: #000000"> addEdge(</span><span style="color: #0000ff">int</span><span style="color: #000000"> from, </span><span style="color: #0000ff">int</span><span style="color: #000000"> to, </span><span style="color: #0000ff">int</span><span style="color: #000000"> weight) {<br />    Node </span><span style="color: #000000">*</span><span style="color: #000000">newNode </span><span style="color: #000000">=</span><span style="color: #000000"> getNode();<br />    newNode</span><span style="color: #000000">-></span><span style="color: #000000">next </span><span style="color: #000000">=</span><span style="color: #000000"> nodeHead[from].next;<br />    newNode</span><span style="color: #000000">-></span><span style="color: #000000">to </span><span style="color: #000000">=</span><span style="color: #000000"> to;<br />    newNode</span><span style="color: #000000">-></span><span style="color: #000000">weight </span><span style="color: #000000">=</span><span style="color: #000000"> weight;<br />    nodeHead[from].next </span><span style="color: #000000">=</span><span style="color: #000000"> newNode;<br />}<br /><br /></span><span style="color: #0000ff">int</span><span style="color: #000000"> main() {<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> rankLimit, goodsCount, substituteCount, subPrice, num, minPrice, minWei;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> minWeiDisUnkPos;<br />    </span><span style="color: #0000ff">int</span><span style="color: #000000"> i, j, from;<br />    scanf(</span><span style="color: #000000">"</span><span style="color: #000000">%d%d</span><span style="color: #000000">"</span><span style="color: #000000">, </span><span style="color: #000000">&</span><span style="color: #000000">rankLimit, </span><span style="color: #000000">&</span><span style="color: #000000">goodsCount);<br />    initGraph(goodsCount </span><span style="color: #000000">+</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">);<br />    </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">; i </span><span style="color: #000000"><=</span><span style="color: #000000"> goodsCount; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />        scanf(</span><span style="color: #000000">"</span><span style="color: #000000">%d%d%d</span><span style="color: #000000">"</span><span style="color: #000000">, price </span><span style="color: #000000">+</span><span style="color: #000000"> i, ownerRank </span><span style="color: #000000">+</span><span style="color: #000000"> i, </span><span style="color: #000000">&</span><span style="color: #000000">substituteCount);<br />        </span><span style="color: #0000ff">for</span><span style="color: #000000"> (j </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">; j </span><span style="color: #000000"><</span><span style="color: #000000"> substituteCount; </span><span style="color: #000000">++</span><span style="color: #000000">j) {<br />            scanf(</span><span style="color: #000000">"</span><span style="color: #000000">%d%d</span><span style="color: #000000">"</span><span style="color: #000000">, </span><span style="color: #000000">&</span><span style="color: #000000">num, </span><span style="color: #000000">&</span><span style="color: #000000">subPrice);<br />            addEdge(i, num, subPrice);<br />        }<br />    }<br />    <br />    minPrice </span><span style="color: #000000">=</span><span style="color: #000000"> price[</span><span style="color: #000000">1</span><span style="color: #000000">];<br />    </span><span style="color: #0000ff">for</span><span style="color: #000000"> (from </span><span style="color: #000000">=</span><span style="color: #000000"> ownerRank[</span><span style="color: #000000">1</span><span style="color: #000000">] </span><span style="color: #000000">-</span><span style="color: #000000"> rankLimit; from </span><span style="color: #000000"><=</span><span style="color: #000000"> ownerRank[</span><span style="color: #000000">1</span><span style="color: #000000">]; from</span><span style="color: #000000">++</span><span style="color: #000000">) {<br />        </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">; i </span><span style="color: #000000"><=</span><span style="color: #000000"> goodsCount; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />            minWeight[i] </span><span style="color: #000000">=</span><span style="color: #000000"> INF;<br />        }<br />        distanceUnknownCount </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />        </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">1</span><span style="color: #000000">; i </span><span style="color: #000000"><=</span><span style="color: #000000"> goodsCount; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />            </span><span style="color: #0000ff">if</span><span style="color: #000000"> (ownerRank[i] </span><span style="color: #000000">>=</span><span style="color: #000000"> from </span><span style="color: #000000">&&</span><span style="color: #000000"> ownerRank[i] </span><span style="color: #000000"><=</span><span style="color: #000000"> from </span><span style="color: #000000">+</span><span style="color: #000000"> rankLimit) {<br />                distanceUnknown[distanceUnknownCount</span><span style="color: #000000">++</span><span style="color: #000000">] </span><span style="color: #000000">=</span><span style="color: #000000"> i;<br />                isDistanceKnown[i] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">false</span><span style="color: #000000">;<br />            }<br />            </span><span style="color: #0000ff">else</span><span style="color: #000000"> {<br />                isDistanceKnown[i] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">true</span><span style="color: #000000">;<br />            }<br />        }<br /><br />        minWeight[</span><span style="color: #000000">1</span><span style="color: #000000">] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />        isDistanceKnown[</span><span style="color: #000000">1</span><span style="color: #000000">] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">false</span><span style="color: #000000">;<br />        </span><span style="color: #0000ff">int</span><span style="color: #000000"> n </span><span style="color: #000000">=</span><span style="color: #000000"> distanceUnknownCount;<br />        </span><span style="color: #0000ff">for</span><span style="color: #000000"> (i </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">; i </span><span style="color: #000000"><</span><span style="color: #000000"> n; </span><span style="color: #000000">++</span><span style="color: #000000">i) {<br />            minWei </span><span style="color: #000000">=</span><span style="color: #000000"> INF;<br />            </span><span style="color: #0000ff">for</span><span style="color: #000000"> (j </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">; j </span><span style="color: #000000"><</span><span style="color: #000000"> distanceUnknownCount; </span><span style="color: #000000">++</span><span style="color: #000000">j) {<br />                </span><span style="color: #0000ff">if</span><span style="color: #000000"> (minWeight[ distanceUnknown[j] ] </span><span style="color: #000000"><</span><span style="color: #000000"> minWei) {<br />                    minWei </span><span style="color: #000000">=</span><span style="color: #000000"> minWeight[ distanceUnknown[j] ];<br />                    minWeiDisUnkPos </span><span style="color: #000000">=</span><span style="color: #000000"> j;<br />                }<br />            }<br />            </span><span style="color: #0000ff">if</span><span style="color: #000000"> (minWei </span><span style="color: #000000">+</span><span style="color: #000000"> price[ distanceUnknown[minWeiDisUnkPos] ] </span><span style="color: #000000"><</span><span style="color: #000000"> minPrice) {<br />                minPrice </span><span style="color: #000000">=</span><span style="color: #000000"> minWei </span><span style="color: #000000">+</span><span style="color: #000000"> price[ distanceUnknown[minWeiDisUnkPos] ];<br />            }<br />            </span><span style="color: #0000ff">for</span><span style="color: #000000"> (Node </span><span style="color: #000000">*</span><span style="color: #000000">tra </span><span style="color: #000000">=</span><span style="color: #000000"> nodeHead[ distanceUnknown[minWeiDisUnkPos] ].next; tra </span><span style="color: #000000">!=</span><span style="color: #000000"> NULL; tra </span><span style="color: #000000">=</span><span style="color: #000000"> tra</span><span style="color: #000000">-></span><span style="color: #000000">next) {<br />                </span><span style="color: #0000ff">if</span><span style="color: #000000"> (</span><span style="color: #000000">!</span><span style="color: #000000">isDistanceKnown[tra</span><span style="color: #000000">-></span><span style="color: #000000">to] </span><span style="color: #000000">&&</span><span style="color: #000000"> <br />                        minWeight[tra</span><span style="color: #000000">-></span><span style="color: #000000">to] </span><span style="color: #000000">></span><span style="color: #000000"> minWeight[ distanceUnknown[minWeiDisUnkPos] ] </span><span style="color: #000000">+</span><span style="color: #000000"> tra</span><span style="color: #000000">-></span><span style="color: #000000">weight ) {<br />                    minWeight[tra</span><span style="color: #000000">-></span><span style="color: #000000">to] </span><span style="color: #000000">=</span><span style="color: #000000"> minWeight[ distanceUnknown[minWeiDisUnkPos] ] </span><span style="color: #000000">+</span><span style="color: #000000"> tra</span><span style="color: #000000">-></span><span style="color: #000000">weight;<br />                }<br />            }<br />            isDistanceKnown[ distanceUnknown[minWeiDisUnkPos] ] </span><span style="color: #000000">=</span><span style="color: #000000"> </span><span style="color: #0000ff">true</span><span style="color: #000000">;<br />            distanceUnknown[minWeiDisUnkPos] </span><span style="color: #000000">=</span><span style="color: #000000"> distanceUnknown[</span><span style="color: #000000">--</span><span style="color: #000000">distanceUnknownCount];<br />        }<br />    }<br />    printf(</span><span style="color: #000000">"</span><span style="color: #000000">%d\n</span><span style="color: #000000">"</span><span style="color: #000000">, minPrice);<br /><br />    </span><span style="color: #0000ff">return</span><span style="color: #000000"> </span><span style="color: #000000">0</span><span style="color: #000000">;<br />}<br /><br /><br /></span></div><img src ="http://www.shnenglu.com/cucumber/aggbug/150262.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/cucumber/" target="_blank">cucumber</a> 2011-07-06 00:58 <a href="http://www.shnenglu.com/cucumber/archive/2011/07/06/150262.html#Feedback" target="_blank" style="text-decoration:none;">鍙戣〃璇勮</a></div>]]></description></item><item><title>poj1860 Currency Exchange: spfa / Bellman Fordhttp://www.shnenglu.com/cucumber/archive/2011/07/04/150078.htmlcucumbercucumberMon, 04 Jul 2011 01:18:00 GMThttp://www.shnenglu.com/cucumber/archive/2011/07/04/150078.htmlhttp://www.shnenglu.com/cucumber/comments/150078.htmlhttp://www.shnenglu.com/cucumber/archive/2011/07/04/150078.html#Feedback0http://www.shnenglu.com/cucumber/comments/commentRss/150078.htmlhttp://www.shnenglu.com/cucumber/services/trackbacks/150078.html闃呰鍏ㄦ枃

cucumber 2011-07-04 09:18 鍙戣〃璇勮
]]> 久久亚洲AV成人无码| 国产精品成人无码久久久久久| 久久精品桃花综合| 久久精品国产男包| 久久人人爽人人爽人人片AV不| 久久露脸国产精品| 人人妻久久人人澡人人爽人人精品| 狠狠色丁香婷婷久久综合| 久久人人爽爽爽人久久久| 久久精品国产99国产电影网| 精品久久久无码中文字幕天天| 久久中文字幕精品| AV无码久久久久不卡蜜桃| 狠狠色丁香婷婷综合久久来来去| 日本精品久久久久影院日本| 一本一本久久aa综合精品| 麻豆av久久av盛宴av| 久久国产精品77777| 久久精品人妻一区二区三区| 久久亚洲AV成人无码| 天天综合久久久网| 久久久精品国产sm调教网站| 久久亚洲电影| 色成年激情久久综合| 久久久久久久女国产乱让韩| 爱做久久久久久| 久久精品国产网红主播| 三级三级久久三级久久| 色综合久久久久网| 久久亚洲精品人成综合网| 色综合合久久天天给综看| www.久久精品| 亚洲精品无码成人片久久| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 久久亚洲精品无码播放| 国产精品久久久久久久久鸭| 久久精品国产男包| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 久久99精品国产| 久久精品国产亚洲av麻豆小说| 亚洲国产成人久久笫一页|