国产人久久人人人人爽,精品国际久久久久999波多野,久久久久久精品免费看SSS

pku 1122

2009年7月29日

題目鏈接：PKU 1122 FDNY to the Rescue!

分類：Diskastra

題目分析與算法原型
有點郁悶，這題由于題目意思沒看仔細加上有些位置沒有理解充分，貢獻了好幾次WA，雖然只是一個Dijkastra的簡單應用，不過此題還是要細心應對的，大致做法是先將輸入的矩陣轉置一下，使得單終點最短路徑變成單源點最短路徑，然后用Dijkastra處理即可（注意題目的一些提示條件，看清楚題目意思）

Code:

1

#include<stdio.h>
2

#include<stdlib.h>
3

#include<string.h>
4

#define max 1000000000
5

#define len 25
6

int n,map[len][len],dis[len],s,adj[len],path[len],visit[len];
8

bool finish;
9

struct node
11

{
12

int dis,num;
13

}place[len];
14

void init()
16

{
17

int i,j;
18

for(i=1;i<=n;i++)
19

for(j=1;j<=n;j++)
20

{
21

if(i==j)map[i][j]=0;
22

else map[i][j]=max;
23

}
24

}
25

int cmp(const void * a,const void * b)
26

{
27

return (*(node *)a).dis > (*(node *)b).dis ? 1:-1;
28

}
29

void Dijkastra(int s)//s為源點
30

{
31

int i,j;
32

for(i=1;i<=n;i++)
33

{
34

dis[i]=map[s][i];
35

visit[i]=0;
36

if(i!=s&&dis[i]<max)path[i]=s;
37

else path[i]=-1;
38

}
39

visit[s]=1;
40

for(i=1;i<n;i++)
41

{
42

int min=max,u;
43

for(j=1;j<=n;j++)
44

if(visit[j]==0&&dis[j]<min)
45

{
46

u=j;
47

min=dis[j];
48

}
49

if(min==max)return;//此語句對于非連通圖是必須的，表示當前已經不存在路徑了
50

visit[u]=1;
51

for(j=1;j<=n;j++)
52

if(visit[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
53

{
54

dis[j]=dis[u]+map[u][j];
55

path[j]=u;
56

}
57

}
58

}
59

int main()
60

{
61

int i,j,pos;
62

while(scanf("%d",&n)!=EOF)
63

{
64

init();
65

finish=false;
66

for(i=1;i<=n;i++)
67

for(j=1;j<=n;j++)
68

{
69

int l;
70

scanf("%d",&l);
71

if(l!=-1)map[j][i]=l;
72

}
73

scanf("%d",&s);
74

pos=0;
75

char ch;
76

memset(adj,0,sizeof(adj));
77

printf("Org\tDest\tTime\tPath\n");
79

while(1)
80

{
81

ch=getchar();
82

if(ch==10)break;
83

while(!(ch>='0'&&ch<='9'))ch=getchar();
84

while(ch>='0'&&ch<='9')
86

{
87

adj[pos]*=10;
88

adj[pos]+=ch-'0';
89

ch=getchar();
90

}
91

if(adj[pos]==s)
93

{
94

printf("%d\t%d\t%d\t%d\n",s,s,0,s);
95

adj[pos]=0;
96

}
97

else pos++;
98

if(ch==10)break;
99

}
100

Dijkastra(s);
101

for(i=0;i<pos;i++)
102

{
103

place[i].dis=dis[adj[i]];
104

place[i].num=adj[i];
105

}
106

qsort(place,pos,sizeof(place[0]),cmp);
107

108

109

for(i=0;i<pos;i++)
110

{
111

printf("%d\t%d\t%d\t%d\t",place[i].num,s,place[i].dis,place[i].num);
112

int kk=path[place[i].num];
113

while(1)
114

{
115

printf("%d",kk);
116

if(kk==s)break;
117

else printf("\t");
118

kk=path[kk];
119

}
120

printf("\n");
121

}
122

}
123

return 0;
124

}

posted on 2009-07-29 20:12 蝸牛也Coding 閱讀(254) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku 1122

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜