比較煩人的模擬
1
#include<stdio.h>
2#include<string.h>
3char xy[30][30],yx[30][30],use[30][30];
4int n,m;
5void di(int x,int y)
6
{
7
if(x>=m||y>=n)return;
8 use[x][y]=0;
9 //printf("%d %d\n",x,y);
10 if(xy[x][y+1]&&use[x-1][y])di(x-1,y);
11 if(xy[x+1][y+1]&&use[x+1][y])di(x+1,y);
12 if(yx[y+1][x+1]&&use[x][y+1])di(x,y+1);
13 if(yx[y][x+1]&&use[x][y-1])di(x,y-1);
14
}
15int main()
16{
17 int ans,i,k,x1,x2,y1,y2,t,j;
18 while(scanf("%d%d",&n,&m),n)
19
{
20 memset(xy,1,sizeof(xy));
21 memset(use,1,sizeof(use));
22 memset(yx,1,sizeof(yx));
23 ans=0;
24 for(i=1;i<=m;i++)yx[0][i]=0;
25 for(i=1;i<=m;i++)yx[n][i]=0;
26 for(i=1;i<=n;i++)xy[0][i]=0;
27 for(i=1;i<=n;i++)xy[m][i]=0;
28 scanf("%d",&k);
29 while(k--)
30 {
31 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
32 if(x1>x2){t=x1;x1=x2;x2=t;}
33 if(y1>y2){t=y1;y1=y2;y2=t;}
34 // printf("asdasdasdas%d %d\n",x1,y1);
35 for(i=y1+1;i<=y2;i++)xy[x1][i]=0;
36 for(i=y1+1;i<=y2;i++)xy[x2][i]=0;
37 for(i=x1+1;i<=x2;i++)yx[y1][i]=0;
38 for(i=x1+1;i<=x2;i++)yx[y2][i]=0;
39
}
40 // printf("asdasdasdas%d\n",xy[1][1]);
41 for(i=0;i<m;i++)
42 for(j=0;j<n;j++)
43 {
44 if(use[i][j] && (xy[i][j+1] || xy[i+1][j+1] || yx[j][i+1] || yx[j+1][i+1]))
45 {
46 //printf("******************\n");
47 di(i,j);
48 ans++;
49 }
50 }
51 for(i=0;i<m;i++)
52 for(j=0;j<n;j++)if(use[i][j])ans++;
53 printf("%d\n",ans);
54
55 }
56 return 0;
57}
58
59
超多的if
1#include<stdio.h>
2char str[500];
3int a[50],ans,j,m,l,t,f[50];
4int main()
5{
6 int KASE,i;
7 scanf("%d",&KASE);
8 gets(str);
9 while(KASE--)
10 {
11 ans=0;j=0;m=0;l=0,t=0;
12 for(i=1;i<=26;i++){a[i]=i;f[i]=0;}
13 gets(str);
14 i=-1;
15 while(str[++i])
16 {
17 if(str[i]==' ');
18 else if(str[i]=='+'){j++;t=1;}
19 else if(str[i]=='-'){m++;t=-1;}
20 else
21 {
22
23 if(j+m==3)
24 {
25 if(j==2)
26 {
27 if(t==1){a[str[i]-'a'+1]++;ans-=a[str[i]-'a'+1];}
28 if(t==-1){a[l]++;ans-=a[str[i]-'a'+1];}
29 }
30 if(j==1)
31 {
32 if(t==1){a[l]--;ans+=a[str[i]-'a'+1];}
33 if(t==-1){a[str[i]-'a'+1]--;ans+=a[str[i]-'a'+1];}
34 }
35 //printf("*******%d\n",ans);
36 }
37 else if(j+m==2)
38 {
39 a[str[i]-'a'+1]+=t;
40 }
41 else if(j+m==1)
42 {
43 ans=ans+a[str[i]-'a'+1]*t;
44 }
45 if(!l)ans=a[str[i]-'a'+1];
46 l=str[i]-'a'+1;
47 f[l]=1;
48 j=0;m=0;
49 //printf("afadfadfadfadf%d %d\n",l,ans);
50 }
51 if(j==2 && m==0 && l){a[l]++;j=0;}
52 if(m==2 && j==0 && l){a[l]--;m=0;}
53 }
54 printf("Expression: %s\n",str);
55 printf("value = %d\n",ans);
56 for(i=1;i<=26;i++)
57 if(f[i])
58 printf("%c = %d\n",i+'a'-1,a[i]);
59 }
60 return 0;
61}
62
63
摘要: 最短路徑問題。把每個點(diǎn)出發(fā)的所有路都存下然后每一個點(diǎn)中按每一個路的出發(fā)時間降序排序。然后就做超多遍最短路徑就可以了
1#include<stdio.h> 2#include<map> 3#include<string> 4#include<string.h>&...
閱讀全文
dfs就可以了。加一個剪枝
1。如果這個人被捉弄后會回到編號小于當(dāng)前編號的點(diǎn)那么這人在這點(diǎn)肯定被捉弄。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char use[110];
int x[110],y[110],t[110],SUM[110];
int best=0;
int KASE,n,f,totle=0;
void di(int k,int sum)
{
totle++;
if(totle>100000000)return;
if(k==n)
{
if(sum>best)best=sum;
return;
}
if(use[k])
{
use[k]=0;
if(k<t[k] && (SUM[t[k]]-SUM[k]+x[k]-x[t[k]]>y[k]));
else di(t[k],sum+y[k]);
use[k]=1;
}
if(use[k]&&t[k]<k);
else di(k+1,sum+x[k]);
}
int main()
{
int i;
srand(406);
scanf("%d",&KASE);
while(KASE--)
{
scanf("%d",&n);
memset(use,1,sizeof(use));
for(i=0;i<n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&t[i]);
t[i]--;
}
SUM[0]=x[i];
for(i=1;i<n;i++)SUM[i]=SUM[i-1]+x[i];
best=0;
di(0,0);
printf("%d\n",best);
}
return 0;
}
高精度的題目
一個高精的的數(shù)乘以int
然后統(tǒng)計(jì)里面k出現(xiàn)的次數(shù)就好了
1#include<stdio.h>
2#include<string.h>
3int a[400][1000];
4int l[400];
5int n,m;
6int main()
7{
8 int t,KASE,ans,i,j;
9 scanf("%d",&KASE);
10 memset(l,-1,sizeof(l));
11 memset(a,0,sizeof(a));
12 a[0][0]=1;l[0]=1;
13 for(i=1;i<=365;i++)
14 {
15 t=l[i-1];
16 for(j=0;j<t;j++)a[i][j]=a[i-1][j]*i;
17 //for(j=t-1;j>=0;j--)printf("%d",a[i][j]);printf("\n");
18 for(j=0;j<t-1;j++)
19 {
20 a[i][j+1]+=a[i][j]/10;
21 a[i][j]%=10;
22 }
23 l[i]=l[i-1];
24/**//*
25 for(j=0;j<t-1;j++)
26 {
27 a[i][j+1]+=a[i][j]/10;
28 a[i][j]%=10;
29 }
30*/
31 while(a[i][l[i]-1]>10)
32 {
33 // printf("asdasdasdasd\n");
34 a[i][l[i]]+=a[i][l[i]-1]/10;
35 a[i][l[i]-1]%=10;
36 l[i]++;
37 }
38 }
39 //printf("%dasdasda",a[4][1]);
40
41 for(i=0;i<KASE;i++)
42 {
43 scanf("%d%d",&n,&m);
44 ans=0;
45 for(j=0;j<l[n];j++)if(a[n][j]==m)ans++;
46 printf("%d\n",ans);
47 }
48 return 0;
49}
50
51
摘要: 很煩人的字符串處理。需要考慮的東西很多用c++寫比較麻煩。自己用c++寫的wa了3次才過。java的話直接正則表達(dá)式就可以了下面分別有c++和java的代碼c++的代碼屬于自己原創(chuàng)java是轉(zhuǎn)來別人的了
1#include<stdio.h> 2int main() 3{ 4 int&nb...
閱讀全文
轉(zhuǎn)自：
http://www.ccw.com.cn/htm/app/aprog/01_7_31_4.asp
| 如果你曾經(jīng)用過Perl或任何其他內(nèi)建正則表達(dá)式支持的語言，你一定知道用正則表達(dá)式處理文本和匹配模式是多么簡單。如果你不熟悉這個術(shù)語，那么“正則表達(dá)式”（Regular Expression）就是一個字符構(gòu)成的串，它定義了一個用來搜索匹配字符串的模式。 |
| 許多語言，包括Perl、PHP、Python、JavaScript和JScript，都支持用正則表達(dá)式處理文本，一些文本編輯器用正則表達(dá)式實(shí)現(xiàn)高級“搜索-替換”功能。那么Java又怎樣呢？本文寫作時，一個包含了用正則表達(dá)式進(jìn)行文本處理的Java規(guī)范需求（Specification Request）已經(jīng)得到認(rèn)可，你可以期待在JDK的下一版本中看到它。 |
| 然而，如果現(xiàn)在就需要使用正則表達(dá)式，又該怎么辦呢？你可以從Apache.org下載源代碼開放的Jakarta-ORO庫。本文接下來的內(nèi)容先簡要地介紹正則表達(dá)式的入門知識，然后以Jakarta-ORO API為例介紹如何使用正則表達(dá)式。 |
| 我們先從簡單的開始。假設(shè)你要搜索一個包含字符“cat”的字符串，搜索用的正則表達(dá)式就是“cat”。如果搜索對大小寫不敏感，單詞“catalog”、“Catherine”、“sophisticated”都可以匹配。也就是說： |
| 假設(shè)你在玩英文拼字游戲，想要找出三個字母的單詞，而且這些單詞必須以“t”字母開頭，以“n”字母結(jié)束。另外，假設(shè)有一本英文字典，你可以用正則表達(dá)式搜索它的全部內(nèi)容。要構(gòu)造出這個正則表達(dá)式，你可以使用一個通配符——句點(diǎn)符號“.”。這樣，完整的表達(dá)式就是“t.n”，它匹配“tan”、“ten”、“tin”和“ton”，還匹配“t#n”、“tpn”甚至“t n”，還有其他許多無意義的組合。這是因?yàn)榫潼c(diǎn)符號匹配所有字符，包括空格、Tab字符甚至換行符： |
| 為了解決句點(diǎn)符號匹配范圍過于廣泛這一問題，你可以在方括號（“[]”）里面指定看來有意義的字符。此時，只有方括號里面指定的字符才參與匹配。也就是說，正則表達(dá)式“t[aeio]n”只匹配“tan”、“Ten”、“tin”和“ton”。但“Toon”不匹配，因?yàn)樵诜嚼ㄌ栔畠?nèi)你只能匹配單個字符： |
| 如果除了上面匹配的所有單詞之外，你還想要匹配“toon”，那么，你可以使用“|”操作符。“|”操作符的基本意義就是“或”運(yùn)算。要匹配“toon”，使用“t(a|e|i|o|oo)n”正則表達(dá)式。這里不能使用方擴(kuò)號，因?yàn)榉嚼ㄌ栔辉试S匹配單個字符；這里必須使用圓括號“()”。圓括號還可以用來分組，具體請參見后面介紹。 |
| 表一顯示了表示匹配次數(shù)的符號，這些符號用來確定緊靠該符號左邊的符號出現(xiàn)的次數(shù)： |
| 假設(shè)我們要在文本文件中搜索美國的社會安全號碼。這個號碼的格式是999-99-9999。用來匹配它的正則表達(dá)式如圖一所示。在正則表達(dá)式中，連字符（“-”）有著特殊的意義，它表示一個范圍，比如從0到9。因此，匹配社會安全號碼中的連字符號時，它的前面要加上一個轉(zhuǎn)義字符“\”。 |
|
圖一：匹配所有123-12-1234形式的社會安全號碼
|
| 假設(shè)進(jìn)行搜索的時候，你希望連字符號可以出現(xiàn)，也可以不出現(xiàn)——即，999-99-9999和999999999都屬于正確的格式。這時，你可以在連字符號后面加上“？”數(shù)量限定符號，如圖二所示： |
|
圖二：匹配所有123-12-1234和123121234形式的社會安全號碼
|
| 下面我們再來看另外一個例子。美國汽車牌照的一種格式是四個數(shù)字加上二個字母。它的正則表達(dá)式前面是數(shù)字部分“[0-9]{4}”，再加上字母部分“[A-Z]{2}”。圖三顯示了完整的正則表達(dá)式。 |
| “^”符號稱為“否”符號。如果用在方括號內(nèi)，“^”表示不想要匹配的字符。例如，圖四的正則表達(dá)式匹配所有單詞，但以“X”字母開頭的單詞除外。 |
| 假設(shè)要從格式為“June 26, 1951”的生日日期中提取出月份部分，用來匹配該日期的正則表達(dá)式可以如圖五所示： |
| 新出現(xiàn)的“\s”符號是空白符號，匹配所有的空白字符，包括Tab字符。如果字符串正確匹配，接下來如何提取出月份部分呢？只需在月份周圍加上一個圓括號創(chuàng)建一個組，然后用ORO API（本文后面詳細(xì)討論）提取出它的值。修改后的正則表達(dá)式如圖六所示： |
|
圖六：匹配所有Month DD,YYYY格式的日期，定義月份值為第一個組
|
| 為簡便起見，你可以使用一些為常見正則表達(dá)式創(chuàng)建的快捷符號。如表二所示： |
| 例如，在前面社會安全號碼的例子中，所有出現(xiàn)“[0-9]”的地方我們都可以使用“\d”。修改后的正則表達(dá)式如圖七所示： |
|
圖七：匹配所有123-12-1234格式的社會安全號碼
|
| 有許多源代碼開放的正則表達(dá)式庫可供Java程序員使用，而且它們中的許多支持Perl 5兼容的正則表達(dá)式語法。我在這里選用的是Jakarta-ORO正則表達(dá)式庫，它是最全面的正則表達(dá)式API之一，而且它與Perl 5正則表達(dá)式完全兼容。另外，它也是優(yōu)化得最好的API之一。 |
| Jakarta-ORO庫以前叫做OROMatcher，Daniel Savarese大方地把它贈送給了Jakarta Project。你可以按照本文最后參考資源的說明下載它。 |
| 我首先將簡要介紹使用Jakarta-ORO庫時你必須創(chuàng)建和訪問的對象，然后介紹如何使用Jakarta-ORO API。 |
| 首先，創(chuàng)建一個Perl5Compiler類的實(shí)例，并把它賦值給PatternCompiler接口對象。Perl5Compiler是PatternCompiler接口的一個實(shí)現(xiàn)，允許你把正則表達(dá)式編譯成用來匹配的Pattern對象。 |
| 要把正則表達(dá)式編譯成Pattern對象，調(diào)用compiler對象的compile()方法，并在調(diào)用參數(shù)中指定正則表達(dá)式。例如，你可以按照下面這種方式編譯正則表達(dá)式“t[aeio]n”： |
| 默認(rèn)情況下，編譯器創(chuàng)建一個大小寫敏感的模式（pattern）。因此，上面代碼編譯得到的模式只匹配“tin”、“tan”、 “ten”和“ton”，但不匹配“Tin”和“taN”。要創(chuàng)建一個大小寫不敏感的模式，你應(yīng)該在調(diào)用編譯器的時候指定一個額外的參數(shù)： |
| 創(chuàng)建好Pattern對象之后，你就可以通過PatternMatcher類用該P(yáng)attern對象進(jìn)行模式匹配。 |
| PatternMatcher對象根據(jù)Pattern對象和字符串進(jìn)行匹配檢查。你要實(shí)例化一個Perl5Matcher類并把結(jié)果賦值給PatternMatcher接口。Perl5Matcher類是PatternMatcher接口的一個實(shí)現(xiàn)，它根據(jù)Perl 5正則表達(dá)式語法進(jìn)行模式匹配： |
| 使用PatternMatcher對象，你可以用多個方法進(jìn)行匹配操作，這些方法的第一個參數(shù)都是需要根據(jù)正則表達(dá)式進(jìn)行匹配的字符串： |
| · boolean matches(String input, Pattern pattern)：當(dāng)輸入字符串和正則表達(dá)式要精確匹配時使用。換句話說，正則表達(dá)式必須完整地描述輸入字符串。 |
| · boolean matchesPrefix(String input, Pattern pattern)：當(dāng)正則表達(dá)式匹配輸入字符串起始部分時使用。 |
| · boolean contains(String input, Pattern pattern)：當(dāng)正則表達(dá)式要匹配輸入字符串的一部分時使用（即，它必須是一個子串）。 |
| 另外，在上面三個方法調(diào)用中，你還可以用PatternMatcherInput對象作為參數(shù)替代String對象；這時，你可以從字符串中最后一次匹配的位置開始繼續(xù)進(jìn)行匹配。當(dāng)字符串可能有多個子串匹配給定的正則表達(dá)式時，用PatternMatcherInput對象作為參數(shù)就很有用了。用PatternMatcherInput對象作為參數(shù)替代String時，上述三個方法的語法如下： |
| · boolean matches(PatternMatcherInput input, Pattern pattern) |
| · boolean matchesPrefix(PatternMatcherInput input, Pattern pattern) |
| · boolean contains(PatternMatcherInput input, Pattern pattern) |
| 下面我們來看看Jakarta-ORO庫的一些應(yīng)用實(shí)例。 |
| 任務(wù)：分析一個Web服務(wù)器日志文件，確定每一個用戶花在網(wǎng)站上的時間。在典型的BEA WebLogic日志文件中，日志記錄的格式如下： |
| 分析這個日志記錄，可以發(fā)現(xiàn)，要從這個日志文件提取的內(nèi)容有兩項(xiàng)：IP地址和頁面訪問時間。你可以用分組符號（圓括號）從日志記錄提取出IP地址和時間標(biāo)記。 |
| 首先我們來看看IP地址。IP地址有4個字節(jié)構(gòu)成，每一個字節(jié)的值在0到255之間，各個字節(jié)通過一個句點(diǎn)分隔。因此，IP地址中的每一個字節(jié)有至少一個、最多三個數(shù)字。圖八顯示了為IP地址編寫的正則表達(dá)式： |
| IP地址中的句點(diǎn)字符必須進(jìn)行轉(zhuǎn)義處理（前面加上“\”），因?yàn)镮P地址中的句點(diǎn)具有它本來的含義，而不是采用正則表達(dá)式語法中的特殊含義。句點(diǎn)在正則表達(dá)式中的特殊含義本文前面已經(jīng)介紹。 |
| 日志記錄的時間部分由一對方括號包圍。你可以按照如下思路提取出方括號里面的所有內(nèi)容：首先搜索起始方括號字符（“[”），提取出所有不超過結(jié)束方括號字符（“]”）的內(nèi)容，向前尋找直至找到結(jié)束方括號字符。圖九顯示了這部分的正則表達(dá)式。 |
| 現(xiàn)在，把上述兩個正則表達(dá)式加上分組符號（圓括號）后合并成單個表達(dá)式，這樣就可以從日志記錄提取出IP地址和時間。注意，為了匹配“- -”（但不提取它），正則表達(dá)式中間加入了“\s-\s-\s”。完整的正則表達(dá)式如圖十所示。 |
| 現(xiàn)在正則表達(dá)式已經(jīng)編寫完畢，接下來可以編寫使用正則表達(dá)式庫的Java代碼了。 |
| 為使用Jakarta-ORO庫，首先創(chuàng)建正則表達(dá)式字符串和待分析的日志記錄字符串： |
| 這里使用的正則表達(dá)式與圖十的正則表達(dá)式差不多完全相同，但有一點(diǎn)例外：在Java中，你必須對每一個向前的斜杠（“\”）進(jìn)行轉(zhuǎn)義處理。圖十不是Java的表示形式，所以我們要在每個“\”前面加上一個“\”以免出現(xiàn)編譯錯誤。遺憾的是，轉(zhuǎn)義處理過程很容易出現(xiàn)錯誤，所以應(yīng)該小心謹(jǐn)慎。你可以首先輸入未經(jīng)轉(zhuǎn)義處理的正則表達(dá)式，然后從左到右依次把每一個“\”替換成“\\”。如果要復(fù)檢，你可以試著把它輸出到屏幕上。 |
| 初始化字符串之后，實(shí)例化PatternCompiler對象，用PatternCompiler編譯正則表達(dá)式創(chuàng)建一個Pattern對象： |
| 現(xiàn)在，創(chuàng)建PatternMatcher對象，調(diào)用PatternMatcher接口的contain()方法檢查匹配情況： |
| 接下來，利用PatternMatcher接口返回的MatchResult對象，輸出匹配的組。由于logEntry字符串包含匹配的內(nèi)容，你可以看到類如下面的輸出： |
| 下面一個任務(wù)是分析HTML頁面內(nèi)FONT標(biāo)記的所有屬性。HTML頁面內(nèi)典型的FONT標(biāo)記如下所示： |
| 程序?qū)凑杖缦滦问剑敵雒恳粋€FONT標(biāo)記的屬性： |
| 在這種情況下，我建議你使用兩個正則表達(dá)式。第一個如圖十一所示，它從字體標(biāo)記提取出“"face="Arial, Serif" size="+2" color="red"”。 |
| 第二個正則表達(dá)式如圖十二所示，它把各個屬性分割成名字-值對。 |
| 現(xiàn)在我們來看看完成這個任務(wù)的Java代碼。首先創(chuàng)建兩個正則表達(dá)式字符串，用Perl5Compiler把它們編譯成Pattern對象。編譯正則表達(dá)式的時候，指定Perl5Compiler.CASE_INSENSITIVE_MASK選項(xiàng)，使得匹配操作不區(qū)分大小寫。 |
| 接下來，創(chuàng)建一個執(zhí)行匹配操作的Perl5Matcher對象。 |
| 假設(shè)有一個String類型的變量html，它代表了HTML文件中的一行內(nèi)容。如果html字符串包含F(xiàn)ONT標(biāo)記，匹配器將返回true。此時，你可以用匹配器對象返回的MatchResult對象獲得第一個組，它包含了FONT的所有屬性： |
| 接下來創(chuàng)建一個PatternMatcherInput對象。這個對象允許你從最后一次匹配的位置開始繼續(xù)進(jìn)行匹配操作，因此，它很適合于提取FONT標(biāo)記內(nèi)屬性的名字-值對。創(chuàng)建PatternMatcherInput對象，以參數(shù)形式傳入待匹配的字符串。然后，用匹配器實(shí)例提取出每一個FONT的屬性。這通過指定PatternMatcherInput對象（而不是字符串對象）為參數(shù)，反復(fù)地調(diào)用PatternMatcher對象的contains()方法完成。PatternMatcherInput對象之中的每一次迭代將把它內(nèi)部的指針向前移動，下一次檢測將從前一次匹配位置的后面開始。 |
| 下面我們來看看另一個處理HTML的例子。這一次，我們假定Web服務(wù)器從widgets.acme.com移到了newserver.acme.com。現(xiàn)在你要修改一些頁面中的鏈接： |
| 執(zhí)行這個搜索的正則表達(dá)式如圖十三所示： |
| 如果能夠匹配這個正則表達(dá)式，你可以用下面的內(nèi)容替換圖十三的鏈接： |
| 注意#字符的后面加上了$1。Perl正則表達(dá)式語法用$1、$2等表示已經(jīng)匹配且提取出來的組。圖十三的表達(dá)式把所有作為一個組匹配和提取出來的內(nèi)容附加到鏈接的后面。 |
現(xiàn)在，返回Java。就象前面我們所做的那樣，你必須創(chuàng)建測試字符串，創(chuàng)建把正則表達(dá)式編譯到Pattern對象所必需的對象，以及創(chuàng)建一個PatternMatcher對象： |
| 接下來，用com.oroinc.text.regex包Util類的substitute()靜態(tài)方法進(jìn)行替換，輸出結(jié)果字符串： |
| Util.substitute()方法的語法如下： |
| 這個調(diào)用的前兩個參數(shù)是以前創(chuàng)建的PatternMatcher和Pattern對象。第三個參數(shù)是一個Substiution對象，它決定了替換操作如何進(jìn)行。本例使用的是Perl5Substitution對象，它能夠進(jìn)行Perl5風(fēng)格的替換。第四個參數(shù)是想要進(jìn)行替換操作的字符串，最后一個參數(shù)允許指定是否替換模式的所有匹配子串（Util.SUBSTITUTE_ALL），或只替換指定的次數(shù)。 |
| 【結(jié)束語】在這篇文章中，我為你介紹了正則表達(dá)式的強(qiáng)大功能。只要正確運(yùn)用，正則表達(dá)式能夠在字符串提取和文本修改中起到很大的作用。另外，我還介紹了如何在Java程序中通過Jakarta-ORO庫利用正則表達(dá)式。至于最終采用老式的字符串處理方式（使用StringTokenizer，charAt，和substring），還是采用正則表達(dá)式，這就有待你自己決定了。 |
最小路徑問題。
求完以后排序就可以了。
這題wa了一次。因?yàn)樽罱鼘懥撕枚嘤邢驁D的然后這個在讀入數(shù)據(jù)的時候忘記考慮這個是一個無向圖了。
1#include<stdio.h>
2#include<string.h>
3int data[300][300],aa,bb,cc,a[300],b[300],n,m,i,j,k,t;
4int main()
5{
6 while(1)
7 {
8 scanf("%d",&n);
9 if(n==0)break;
10 scanf("%d",&m);
11 memset(data,3,sizeof(data));
12 for(i=0;i<m;i++)
13 {
14 scanf("%d%d%d",&aa,&bb,&cc);
15 data[aa][bb]=cc;
16 data[bb][aa]=cc;
17 }
18 for(i=0;i<n;i++)data[i][i]=0;
19 for(k=0;k<n;k++)
20 for(i=0;i<n;i++)
21 for(j=0;j<n;j++)
22 if(data[i][k]+data[k][j]<data[i][j])
23 data[i][j]=data[i][k]+data[k][j];
24 for(i=0;i<n;i++)a[i]=data[0][i];
25 for(i=0;i<n;i++)b[i]=i;
26 for(i=0;i<n;i++)
27 for(j=0;j<n-1;j++)
28 if((a[j]>a[j+1]) || ((a[j]==a[j+1])&& b[j]>b[j+1]))
29 {
30 t=a[j];
31 a[j]=a[j+1];
32 a[j+1]=t;
33 t=b[j];
34 b[j]=b[j+1];
35 b[j+1]=t;
36 }
37
38 scanf("%d",&k);
39 printf("%d\n",b[k]);
40 }
41 return 0;
42}
43