Problem
Angel最近无聊，去了圣诞岛(CX *^_^*)，他喜欢无目的的乱逛，当然，他不会轻易地回头。Angel想去广场，那么，他什么时候才能到呢？你已经得到了CX的地图，地图上有N(N <= 100)个交叉路口，交叉路口之间有马路相连接(不超过1000条马路)。因为CX的人遵循奇怪的规则，道路都是单向的，不同的道路之间有一定的距离，我们假设Angel所在的地点为点1，广场所在点为N。假设Angel走一单位距离需要一单位时间。问Angel最早和最迟什么时候到达广场？
Input
本题有多组数据，第一行N, M，M是边的数量以后M行，每行3个整数X, Y, Weight，代表一条从X城市到Y城市，长度为Wweight的边。
Output
每组数据，第一行是最少时间，第二行是最迟时间，要是可怜的Angel可能永远到不了广场，输出一行Never。
Sample Input
5 5
1 2 1
1 4 10
2 3 1
3 4 1
4 5 1
Sample Output
4
11
来源：http://acm.tongji.edu.cn/showproblem.php?problem_id=1098
最新评论发表评论
您尚未登陆本站，不能发表评论，请登陆
评论人: MissJuliet 发布时间: 2011-6-27 11:30:05
Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire
Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below.
http://www.PaisaLive.com/register.asp?3556638-4847933
After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator.
Miss Juliet
Admin paisalive.com
评论人: yani423 发布时间: 2011-5-25 12:39:01
#include using namespace std; #define INF 1000000000 /*typedef struct node { int x; int y; int len; }path; path paths[1001];*/ int n,k; int graph[101][101]; int dmax[101]; int dmin[101]; void in_init() { int i,j,x,y; memset(graph,0,sizeof(graph)); for(i=0;i cin>>x>>y; cin>>graph[x][y]; } dmax[1]=-1; dmin[1]=INF; for(i=2;i<=n;i++) { dmax[i]=-1; dmin[i]=INF; } } void dijkstra() { int i,j; dmin[1]=0; dmax[1]=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(graph[i][j]&&dmin[i] { dmin[j]=dmin[i]+graph[i][j]; } if(graph[i][j]&&dmax[i]>-1&&dmax[j] dmax[j]=dmax[i]+graph[i][j]; } } } cout< int main() { while(cin>>n>>k) { in_init(); dijkstra(); } } 用dijkstra算法···每次更新到第i个节点的最短路径 评论人: xulangxiaoyao 发布时间: 2011-3-29 22:15:10 呵呵，给你最少时间那个问的。 很简单的回溯，没进行任何优化。 欢迎高手指正! #include void backtrack(int ); int arc[100][100],t[100]; int HS=0, best=0x0fffffff; int N,M; int main() { //获得数据 scanf("%d %d", &N, &M); for(int i=0; i else arc[i][j]=0x0fffffff; } for(i=0; i scanf("%d %d %d", &x, &y, &weight); arc[x-1][y-1] = weight; } //回溯 backtrack(0); //输出最少时间结果 printf("%d\\n", best); return 0; } void backtrack(int i) { for( int j = 1 ; j < N ; j++) { if ( HS + arc[i][j] < best && !t[j] ) { t[j] = 1; HS+=arc[i][j]; backtrack(i+1); t[j] = 0; HS-=arc[i][j]; } if ( j == N-1 ) { if ( HS + arc[i][j] < best ) best = HS+arc[i][j];} } } 评论人: qtech_hemiao@126.com 发布时间: 2011-3-17 18:26:47 麻烦那位高手给个解题的方案啊... 只是看代码感觉很吃力啊。 不用太详细，简单的介绍一下就行了... 评论人: xiaoba 发布时间: 2011-3-8 23:06:39 java党路过： import java.io.*; import java.util.*; public class Cac { private static int n,n1; private int min,max,min1,max1,k; private boolean bb=true; private static Object[] O1; private ArrayList private ArrayList private ArrayList private static int[][] a; public static String read(){ StringBuilder sb=new StringBuilder(); try{ BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); try{ String s; for(int i=0;i<6;i++){ s=in.readLine(); sb.append(s); sb.append("\\n"); } }finally{ in.close(); } }catch(IOException e){ throw new RuntimeException(e); } return sb.toString(); } public void go(int b){ aa.clear(); ab.clear(); for(int i=0;i aa.add(i); ab.add(a[i][2]); } } while(bb){ k++; if(k<10){ min=Collections.min(ab); min1=min1+min; if(aa.size()>1){ for(Integer ii:aa){ if(a[ii][2]==min){ ac.add(a[ii][1]); } } if(ac.size()>1){ if(a[aa.get(0)][1]==n){ bb=false; } go(Collections.max(ac)); }else{ if(ac.get(0)==n){ bb=false; } go(ac.get(0)); } }else{ if(a[aa.get(0)][1]==n){ bb=false; } go(a[aa.get(0)][1]); } }else{ bb=false; System.out.println("Angel可能永远到不了广场"); } ac.clear(); } } public void come(int b){ aa.clear(); ab.clear(); for(int i=0;i aa.add(i); ab.add(a[i][2]); } } while(bb){ k++; if(k<10){ max=Collections.max(ab); max1=max+max1; if(aa.size()>1){ for(Integer ii:aa){ if(a[ii][2]==max){ ac.add(a[ii][1]); } } if(ac.size()>1){ if(aa.get(0)==(n-1)){ bb=false; } come(Collections.min(ac)); }else{ if(ac.get(0)==n){ bb=false; }else{ come(ac.get(0)); } } }else{ if(a[aa.get(0)][1]==n){ bb=false; } come(a[aa.get(0)][1]); } }else{ bb=false; System.out.println("Angel可能永远到不了广场"); } ac.clear(); } } public static void main(String[] args){ Cac c=new Cac(); ArrayList O1=ad.toArray(); n=Integer.parseInt(O1[1].toString()); a=new int[n][n]; for(int i=0;i<(O1.length-2)/3;i++){ for(int j=0;j<3;j++){ a[i][j]=Integer.parseInt(O1[n1+2].toString()); n1++; } } c.go(1); System.out.println(c.min1); c.bb=true; c.come(1); System.out.println(c.max1); } } 5 5 1 2 20 1 4 10 2 3 1 3 4 20 4 5 1 //output 11 42 评论人: harpe1999 发布时间: 2010-4-27 11:59:27 简简单单，轻轻松松搞定了！！ #include #include #include using namespace std; struct road{ int st; int ed; int w; }; int main(int argc, char *argv[]) { //ifstream inf("input.txt"); string str; //getline(inf,str); getline(cin,str); int line,end; sscanf(str.c_str(),"%d %d",&line,&end); road * p=new road[line]; int i=0; while(i //getline(inf,str); getline(cin,str); sscanf(str.c_str(),"%d %d %d",&p[i].st,&p[i].ed,&p[i].w); i++; } int *pw=new int[line+1]; int *pb=new int[line+1]; for(int i=1;i pb[1]=0; for(int i=0;i int tmp2=pb[p[i].st]+p[i].w; if(tmp2>pb[p[i].ed] || pb[p[i].ed]==-1)pb[p[i].ed]=tmp2; int tmp=pw[p[i].st]+p[i].w; if(tmp if(pb[5]==-1)cout<<"never"< cout< delete []p; delete []pw; delete []pb; system("PAUSE"); return EXIT_SUCCESS; } 评论人: iipulei 发布时间: 2010-4-6 17:07:09 Dijkstra算法？ 评论人: davyjang 发布时间: 2010-2-21 13:57:12 用了很暴力的回溯递归，希望指正！:-D #include"stdio.h" int m=0,n=0,way[100][100],pathlengh=0,result[100]={NULL},count_result=0; void find(int depth) { if(depth==m-1) { result[count_result]=pathlengh; count_result+=1; } else { int t=depth+1; for(;t if(way[depth][t]!=65536) { pathlengh+=way[depth][t]; find(t); pathlengh-=way[depth][t]; } else continue; } return; } } void main() { scanf("%d%d",&m,&n); for(int i=0;i int t1=0,t2=0,t3=0; for( i=0;i scanf("%d%d%d",&t1,&t2,&t3); way[t1-1][t2-1]=t3; } find(0); int min,max; if(count_result==0) printf("Never!\\n"); else {min=max=result[0]; for(i=1;i if(result[i] if(result[i]>max) max=result[i]; } printf("%d\\n",min); printf("%d\\n",max);} } 评论人: qq3344521 发布时间: 2009-4-23 15:44:28 #include #include #ifdef _DEBUG #include #endif #define MAX_N 100 #define MAX_M 1000 #define COST_IFINITE -1 int n,m; struct _List { int vertex; int cost; _List *next; }; struct Vertex_t { Vertex_t() : cost(COST_IFINITE), parent(0), isVisited(false), head(NULL), worstCost(COST_IFINITE) {/**/} _List *head; int cost; int parent; bool isVisited; int worstParent; int worstCost; }; Vertex_t vertics[MAX_N+1]; int min_cost,max_cost; Vertex_t *min_who,*max_who; void ReadGraph(FILE *file) { int i=m; while(i-- > 0) { int a,b,c; fscanf(file,"%d %d %d\\n",&a,&b,&c); _List *p = new _List; p->vertex = b; p->cost = c; p->next = NULL; if(vertics[a].head == NULL) { vertics[a].head = new _List; vertics[a].head->vertex = a; vertics[a].head->next = p; }else { p->next = vertics[a].head->next; vertics[a].head->next = p; } } } void Resolve(int toVisit,int cost,Vertex_t *who) { if(toVisit < 1 || toVisit > n) return; if(!vertics[toVisit].isVisited) { vertics[toVisit].isVisited = true; vertics[toVisit].cost = who->cost + cost; vertics[toVisit].parent = who->head->vertex; vertics[toVisit].worstCost = who->worstCost + cost; vertics[toVisit].worstParent = who->head->vertex; }else { if(vertics[toVisit].cost > who->cost + cost) { vertics[toVisit].cost = who->cost + cost; vertics[toVisit].parent = who->head->vertex; } if(vertics[toVisit].worstCost < who->worstCost + cost) { vertics[toVisit].worstCost = who->worstCost + cost; vertics[toVisit].worstParent = who->head->vertex; }else return; } if(toVisit == n) { if(!min_who || cost + who->cost < min_cost) { min_cost = cost + who->cost; min_who = who; } if(!max_who || who->worstCost + cost > max_cost) { max_who = who; max_cost = who->worstCost + cost; } return; } _List *p = vertics[toVisit].head->next; while(p) { Resolve(p->vertex,p->cost,&vertics[toVisit]); p = p->next; } } int main() { vertics[1].cost = 0; vertics[1].worstCost = 0; FILE *fp = fopen("data.dat fscanf(fp,"%d %d\\n",&n,&m); ReadGraph(fp); _List *p = vertics[1].head->next; while(p) { Resolve(p->vertex,p->cost,&vertics[1]); p = p->next; } if(min_who == NULL) { printf("Impossible!\\n"); return 0; } printf("min %d\\n",min_cost); if(max_who == NULL) { printf("Impossible!\\n"); return 0; } printf("max %d\\n",max_cost); #ifdef _DEBUG { Vertex_t *pv = min_who; using std::stack; stack path.push(n); while(pv->parent) { path.push(pv->head->vertex); pv = &vertics[pv->parent]; } path.push(1); while(path.size() != 0) { printf("%d ",path.top()); path.pop(); } printf("\\n"); } { Vertex_t *pv = max_who; using std::stack; stack path.push(n); while(pv->worstParent) { path.push(pv->head->vertex); pv = &vertics[pv->worstParent]; } path.push(1); while(path.size() != 0) { printf("%d ",path.top()); path.pop(); } printf("\\n"); } #endif //_DEBUG return 0; } //data.dat 5 5 1 2 20 1 4 10 2 3 1 3 4 20 4 5 1 //output min 11 max 42 1 4 5 1 2 3 4 5 Press any key to continue 评论人: forloop 发布时间: 2009-1-15 14:01:44 } if(vertics[toVisit].worstCost < who->worstCost + cost) //少了个else补上. }else if(vertics[toVisit].worstCost < who->worstCost + cost) 评论人: forloop 发布时间: 2009-1-15 13:52:11 #include #include #ifdef _DEBUG #include #endif #define MAX_N 100 #define MAX_M 1000 #define COST_IFINITE -1 int n,m; struct _List { int vertex; int cost; _List *next; }; struct Vertex_t { Vertex_t() : cost(COST_IFINITE), parent(0), isVisited(false), head(NULL), worstCost(COST_IFINITE) {/**/} _List *head; int cost; int parent; bool isVisited; int worstParent; int worstCost; }; Vertex_t vertics[MAX_N+1]; int min_cost,max_cost; Vertex_t *min_who,*max_who; void ReadGraph(FILE *file) { int i=m; while(i-- > 0) { int a,b,c; fscanf(file,"%d %d %d\\n",&a,&b,&c); _List *p = new _List; p->vertex = b; p->cost = c; p->next = NULL; if(vertics[a].head == NULL) { vertics[a].head = new _List; vertics[a].head->vertex = a; vertics[a].head->next = p; }else { p->next = vertics[a].head->next; vertics[a].head->next = p; } } } void Resolve(int toVisit,int cost,Vertex_t *who) { if(toVisit < 1 || toVisit > n) return; if(!vertics[toVisit].isVisited) { vertics[toVisit].isVisited = true; vertics[toVisit].cost = who->cost + cost; vertics[toVisit].parent = who->head->vertex; vertics[toVisit].worstCost = who->worstCost + cost; vertics[toVisit].worstParent = who->head->vertex; }else { if(vertics[toVisit].cost > who->cost + cost) { vertics[toVisit].cost = who->cost + cost; vertics[toVisit].parent = who->head->vertex; } if(vertics[toVisit].worstCost < who->worstCost + cost) { vertics[toVisit].worstCost = who->worstCost + cost; vertics[toVisit].worstParent = who->head->vertex; }else return; } if(toVisit == n) { if(!min_who || cost + who->cost < min_cost) { min_cost = cost + who->cost; min_who = who; } if(!max_who || who->worstCost + cost > max_cost) { max_who = who; max_cost = who->worstCost + cost; } return; } _List *p = vertics[toVisit].head->next; while(p) { Resolve(p->vertex,p->cost,&vertics[toVisit]); p = p->next; } } int main() { vertics[1].cost = 0; vertics[1].worstCost = 0; FILE *fp = fopen("data.dat fscanf(fp,"%d %d\\n",&n,&m); ReadGraph(fp); _List *p = vertics[1].head->next; while(p) { Resolve(p->vertex,p->cost,&vertics[1]); p = p->next; } if(min_who == NULL) { printf("Impossible!\\n"); return 0; } printf("min %d\\n",min_cost); if(max_who == NULL) { printf("Impossible!\\n"); return 0; } printf("max %d\\n",max_cost); #ifdef _DEBUG { Vertex_t *pv = min_who; using std::stack; stack path.push(n); while(pv->parent) { path.push(pv->head->vertex); pv = &vertics[pv->parent]; } path.push(1); while(path.size() != 0) { printf("%d ",path.top()); path.pop(); } printf("\\n"); } { Vertex_t *pv = max_who; using std::stack; stack path.push(n); while(pv->worstParent) { path.push(pv->head->vertex); pv = &vertics[pv->worstParent]; } path.push(1); while(path.size() != 0) { printf("%d ",path.top()); path.pop(); } printf("\\n"); } #endif //_DEBUG return 0; } //data.dat 5 5 1 2 20 1 4 10 2 3 1 3 4 20 4 5 1 //output min 11 max 42 1 4 5 1 2 3 4 5 Press any key to continue 评论人: pengyanxia0414 发布时间: 2008-12-10 22:46:54 请问一下，这个题目好像在TC中运行不了啊，怎么搞的啊，哪位高人指点指点啊 ！！！！！！！ 急需解答！！！！ 谢谢！！！！！ 评论人: yxysdcl 发布时间: 2008-11-2 12:17:30 最短路径可以由floyd求，最长路的话，因为路径中没有权值为负的，所以也可以用floyd，如果有负权的图的最长路，可以用bellman 评论人: 神愚嘻嘻 发布时间: 2008-10-25 18:48:22 这一题用Floyed 评论人: 神愚嘻嘻 发布时间: 2008-10-25 18:44:14 你验证过吗？ 评论人: YslayerY 发布时间: 2008-8-2 17:23:46 #include #include struct node; struct node_link { node * neib; int weight; node_link * next; }; struct node { int city; node_link * head_neighbour; node_link * end_neighbour; }; node * cx; int ns; int input() { int n; int m; node_link * tmp; scanf("%d",&n); cx= new node[n]; ns=n; scanf("%d",&m); int s; int t; int w; for(int i=1;i<=m;i++) { scanf("%d %d %d",&s,&t,&w); tmp=new node_link; tmp->neib=&cx[t-1]; tmp->weight=w; tmp->next=NULL; if(cx[s-1].head_neighbour == NULL) { cx[s-1].head_neighbour = tmp; cx[s-1].end_neighbour = tmp; continue; } cx[s-1].end_neighbour->next=tmp; cx[s-1].end_neighbour=tmp; } return 0; } void cal(int * max,int * min,node * now,int time) { int m=0; int n=100000; node_link * link= now->head_neighbour; while(link != NULL) { if(link->neib == &cx[ns-1]) { if((*min) > (time + link->weight)) *min=(time+link->weight); if((*max) < (time + link->weight)) *max=(time+link->weight); link = link->next; continue; } cal(max,min,link->neib,time+link->weight); link = link->next; } } int main(int argc,char ** argv) { int max=0; int min=1000000; input(); cal(&max,&min,&cx[0],0); printf("%d\\n%d\\n",min,max); return 0; } 评论人: yanzioUo 发布时间: 2008-7-31 11:08:13 哪位高手用c写个程序吧,期待着哈! 是不是要用到收据结构啊,,,,,,, 评论人: yeyegm 发布时间: 2007-5-6 19:40:58 var i,j,k,s,t,m,n,x,y,z:longint; b:array[1..100,1..100] of longint; begin read(n,m); for i:=1 to m do begin read(x,y,z); b[x,y]:=z; end; for i:=1 to m-1 do for j:=i+1 to m do for k:=i to j-1 do if (b[i,k]+b[k,j]>b[i,j]) and(b[k,j]<>0) then b[i,j]:=b[i,k]+b[k,j]; write(b[1,n]); end. 这是最大值，最小值把‘>'转换成‘<’就行，就是也许会超速，简单的DP～
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
